Reproduce “Distinguished In Uniform: Self Attention Vs. Virtual Nodes” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Eran Rosenbluth, Jan Tönshoff, Martin Ritzert, Berke Kisin, Martin Grohe
Researchers from RWTH Aachen University and Georg-August-Universität Göttingen rigorously compared Graph Transformers and Message-Passing GNNs with Virtual Nodes based on their uniform expressivity. The study concluded that neither architecture is uniformly universal, and they exhibit incomparable expressiveness, each capable of expressing functions the other cannot.
Key insights
- Neither Graph Transformers nor Message-Passing GNNs with Virtual Nodes are universal approximators in the uniform setting, meaning a single network cannot generalize to all possible graph sizes without performance degradation.
- Graph Transformers and Message-Passing GNNs with Virtual Nodes possess incomparable expressiveness; each architecture can uniformly express certain functions that the other cannot.
- The uniform universality of Graph Transformers, often highlighted as an advantage, is not unique, as even shallow Message-Passing GNNs and MLPs can achieve non-uniform universality with appropriate positional encodings.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.