Self-Attention vs Virtual Nodes in Graph Neural Networks: What Really Works?

1. Basic Information

Paper title: Distinguished in Uniform: Self-Attention vs. Virtual Nodes

Authors: Eran Rosenbluth, Jan Tönshoff, Martin Ritzert, Berke Kisin, Martin Grohe

Affiliations: RWTH Aachen University; Georg-August-Universität Göttingen

2. Introduction

Graph Transformers (e.g., SAN, GPS) combine message‑passing GNNs with global self‑attention to process graph data. Prior work shows they are universal function approximators, but they have two reservations: (1) initial node features must include positional encodings, and (2) the approximators are non‑consistent—different graph sizes may require different networks.

The paper clarifies that this lack of consistency is not unique to Graph Transformers; pure MPGNNs and even two‑layer MLPs with the same positional encodings also fail to be consistent universal approximators. The authors then focus on *consistent expressive power*: a single network should approximate a target function for graphs of all sizes. They compare Graph Transformers with a more efficient MPGNN + Virtual Node (VN) architecture, highlighting the fundamental difference in global computation—self‑attention versus a virtual node.

The main contribution is proving that, regarding consistent expressive power, MPGNN + VN and Graph Transformers cannot replace each other. Synthetic experiments support the theory, and real‑world datasets show mixed results, indicating no clear superiority in practice.

3. Methods

The study examines the consistency of approximation between Graph Transformers (GT) and MPGNN + VN.

The authors first assume that positional encodings are graph‑isomorphic and prove that a 2‑layer MLP and a 1‑layer MPGNN are universal function approximators under this assumption.

Next, they show that both GT and MPGNN + VN are *not* consistent universal approximators. By constructing specific target functions (e.g., graph 3‑colorability), they demonstrate that GPS (a Graph Transformer variant) cannot consistently approximate certain functions, whereas MPGNN + VN with a sum‑readout can.

Conversely, they construct another target function that GPS can compute exactly while MPGNN + VN cannot, establishing that the two families are incomparable in consistent expressive power.

4. Experimental Findings

Synthetic experiments validate the theoretical claims.

Results show MPGNN + VN perfectly predicts target functions on larger graphs outside the training distribution, while GPS performance degrades rapidly on larger graphs, matching theoretical prediction.

On real datasets, results are mixed:

LRGB peptides: all models perform similarly; neither MPGNN + VN nor Graph Transformer shows clear advantage.

PascalVOC‑SP: GatedGCN + VN and GPS perform comparably, indicating virtual nodes match self‑attention on this task.

ogbg‑molpcba: GatedGCN + VN achieves the best performance, about 1 % higher average accuracy than other methods.

Overall, MPGNN + VN is competitive with Graph Transformers on real‑world tasks.

5. Conclusion

The paper compares Graph Transformers and MPGNN + VN in terms of consistent expressive power. Theoretically, both are not consistent universal approximators, and each can represent functions that the other cannot, making them incomparable.

Synthetic experiments confirm that when a target function is consistently representable by one model family but not the other, the former exhibits superior generalization.

Real‑world experiments yield mixed outcomes, with both families performing similarly overall; however, MPGNN + VN can achieve state‑of‑the‑art results on certain benchmarks, demonstrating that a simple virtual node can match the effectiveness of self‑attention in many cases.

In one sentence: in graph learning, attention is often not all you need.