Research map / Graph learning / GNN architectures
Distinguished In Uniform: Self-Attention Vs. Virtual Nodes
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.
Compares graph transformers (GPS/SAN-style self-attention) with message-passing GNNs plus virtual nodes in the uniform expressivity setting, proving neither subsumes the other, and supports this with synthetic and benchmark experiments.
Problem
Graph transformers are often called universal approximators, but that holds only non-uniformly (network may depend on graph size) and with positional encodings. The paper asks how GTs and MPGNN+virtual-node models compare in uniform expressivity, where one network must handle graphs of all sizes.
Approach
Shows that non-uniform universality via injective positional encodings is shared by MPGNNs and even 2-layer MLPs, then proves in the uniform setting that GPS and MPGNN+VN are not universal and are mutually incomparable: GPS cannot compute |V|^2 uniformly, while GPS computes a specific attention-based function that MPGNN+VN cannot.
Key results
- On the synthetic |V|^2 task, GCN-based MPGNN+VN learned the function accurately even for test graphs up to size 200, while GPS error rose sharply beyond the training size of 50.
- On the synthetic h(G_{l,r}) task, MAE grew roughly linearly for both models, with the MPGNN+VN error increasing about twice as fast as GPS when extrapolating to l,r up to 50.
- On LRGB/OGB benchmarks results were mixed: GatedGCN-VN reached 0.4477 F1 on PascalVOC-SP vs GPS 0.4440, and 0.3141 AP on ogbg-molpcba, while GPS led on COCO-SP (0.3884 vs 0.3244).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add a virtual node to GatedGCN | GatedGCN · PASCALVOC-SP | Test F1: 0.3880 ± 0.0040 -> 0.4477 ± 0.0137 | Helped |
| add a virtual node to GatedGCN | GatedGCN · COCO-SP | Test F1: 0.2922 ± 0.0018 -> 0.3244 ± 0.0025 | Helped |
| add a virtual node to GatedGCN | GatedGCN · PEPTIDES-FUNC | Test AP: 0.6765 ± 0.0047 -> 0.6823 ± 0.0069 | No clear effect |
| add a virtual node to GatedGCN | GatedGCN · PEPTIDES-STRUCT | Test MAE: 0.2477 ± 0.0009 -> 0.2475 ± 0.0018 | No clear effect |
| add a virtual node to GatedGCN | GatedGCN · OGB-CODE2 | Test F1: 0.1606 ± 0.0015 -> 0.1855 ± 0.0018 | Helped |
| add a virtual node to GatedGCN | GatedGCN · OGB-MolPCBA | Test AP: 0.3066 ± 0.0013 -> 0.3141 ± 0.0019 | Helped |
Surprising findings
- Two-layer MLPs and one-layer MPGNNs with injective positional encodings are already non-uniform universal approximators, so universality of graph transformers is not specific to attention.
- On several real-world benchmarks a simple virtual node matches or beats graph transformers, e.g. GatedGCN-VN sets state-of-the-art on ogbg-molpcba.
Limitations
- Theoretical separation relies on specific constructed functions (|V|^2 and h(G_{l,r})) and does not characterize the full uniform expressivity classes.
- Uniform universal approximation is shown impossible only for PTIME-computable positional encodings and bounded-range assumptions.
- Real-world results are mixed and the paper does not isolate the effect of the global mechanism from other design choices.
Experimental setup
Datasets: synthetic random graphs (|V|^2 target) synthetic G_{l,r} graphs peptides-func peptides-struct PascalVOC-SP COCO-SP ogbg-code2 ogbg-molpcba
Benchmarks: peptides-func peptides-struct PascalVOC-SP COCO-SP ogbg-code2 ogbg-molpcba synthetic |V|^2 regression synthetic h(G_{l,r}) regression
Metrics: relative error MAE F1 AP
Baselines: GPS SAN LGI-GT Exphormer GCN GINE GatedGCN GCN-VN GatedGCN-VN
Builds on: GPS LapPE GCN GatedGCN
Closest papers by meaning
- Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs (ICLR 2025 · similarity 0.88)
- What Expressivity Theory Misses: Message Passing Complexity for GNNs (NeurIPS 2025 · similarity 0.88)
- Generalizable Insights for Graph Transformers in Theory and Practice (NeurIPS 2025 · similarity 0.87)
- Polynormer: Polynomial-Expressive Graph Transformer in Linear Time (ICLR 2024 · similarity 0.87)
- Towards Principled Graph Transformers (NeurIPS 2024 · similarity 0.87)
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 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.