Research map / Graph learning / GNN architectures
Primphormer: Efficient Graph Transformers with Primal Representations
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 Primphormer, a graph Transformer that replaces pairwise self-attention with a primal-dual (asymmetric kernel) primal representation using a virtual-node projection, giving linear-in-N complexity while retaining universal approximation and 1-WL expressivity.
Problem
Graph Transformers have quadratic complexity in the number of nodes due to pairwise attention, limiting scalability to large graphs; existing linear/sparse alternatives add overhead or lose efficiency on dense graphs.
Approach
Interprets graph self-attention as a dual representation of an asymmetric kernel machine, derives a primal form via a virtual-node global projection and a primal-dual objective, and enforces it by adding a loss driving the primal objective to zero, so attention is computed without pairwise scores.
Key results
- Primphormer reaches 0.4602 F1 on PascalVOC-SP versus 0.3748 for GraphGPS (full attention) and 0.3975 for Exphormer.
- On BREC, Primphormer with SPE scores 219.4 total versus 213 for standard Transformer and 171.4 for Primal-Atten.
- On ogbn-products Primphormer uses about 13.35 GB peak memory versus OOM for full Transformer in GPS, with 22.1 s/epoch.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the GPS attention with Primphormer | GPS · PascalVOC-SP | F1: 0.3975 ± 0.0037 -> 0.4602 ± 0.0077 | Helped |
| Replace the GPS attention with Primphormer | GPS · Peptides-Func | AP: 0.6527 ± 0.0043 -> 0.6612 ± 0.0065 | Helped |
| Replace the GPS attention with Primphormer | GPS · CIFAR10 | accuracy: 74.69 ± 0.125 -> 74.13 ± 0.241 | Hurt |
| Replace the GPS attention with Primphormer | GPS · MalNet-Tiny | accuracy: 94.02 ± 0.209 -> 93.62 ± 0.242 | Hurt |
| Replace the GPS attention with Primphormer | GPS · ogbn-products | accuracy: 74.67 ± 0.179 -> 74.89 ± 0.281 | Helped |
| Replace the GPS attention with Primphormer | GPS · CIFAR10, MalNet-Tiny, PascalVOC-SP, Peptides-Func, ogbn-products | running time | Mixed |
Surprising findings
- Primphormer does not clearly beat Exphormer on CIFAR10 (74.13 vs 74.69) and MalNet-Tiny (93.62 vs 94.02).
Limitations
- Relies on a penalty loss to approximate KKT points rather than exact solution, so primal-dual equivalence holds only approximately.
- Edge features are not incorporated into the primal representation.
- Does not clearly outperform Exphormer on several benchmarks.
Experimental setup
Datasets: CIFAR10 MNIST PascalVOC-SP COCO-SP PATTERN CLUSTER MalNet-Tiny Peptides-Func Peptides-Struct PCQM-Contact ogbn-products BREC
Benchmarks: LRGB CIFAR10 MNIST PATTERN CLUSTER MalNet-Tiny ogbn-products BREC
Metrics: F1 AP MAE MRR accuracy running time per epoch peak memory (GB)
Baselines: GraphGPS Exphormer BigBird Performer Primal-Atten Graphormer APE-GT SAN EGT GatedGCN
Builds on: GraphGPS Primal-Atten (Chen et al. 2023) Exphormer asymmetric kernel trick (Lin et al. 2022) least squares SVM variational principle (Suykens 2016)
Closest papers by meaning
- What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding (ICML 2024 · similarity 0.88)
- Polynormer: Polynomial-Expressive Graph Transformer in Linear Time (ICLR 2024 · similarity 0.87)
- Generalizable Insights for Graph Transformers in Theory and Practice (NeurIPS 2025 · similarity 0.87)
- Even Sparser Graph Transformers (NeurIPS 2024 · similarity 0.87)
- Unifying and Enhancing Graph Transformers via a Hierarchical Mask Framework (NeurIPS 2025 · similarity 0.86)
- VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections (ICLR 2024 · similarity 0.86)
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.