最近、Graph Transformer（GT）はグラフ学習アルゴリズムの新たなパラダイムとして登場し、複数のベンチマークにおいて従来の主流であったメッセージパッシングニューラルネットワーク（MPNN）を上回る性能を示している。Kimら（2022年）の先行研究では、適切な位置埋め込み（position embedding）を用いることで、GTはMPNNを任意の精度で近似可能であることが示されており、これによりGTはMPNN以上に表現力を持つことが示唆されている。本論文では、この関係の逆を検討し、理論的根拠が乏しいものの広く用いられているヒューリスティックである仮想ノード（Virtual Node, VN）を導入したMPNNが、GTの自己注意（self-attention）層を任意に近似可能であることを示す。具体的には、まず、線形トランスフォーマーの一種であるPerformer／Linear Transformer（Choromanskiら、2020年；Katharopoulosら、2020年）に対して、深さO(1)、幅O(1)のMPNN＋VNが、その自己注意層を近似可能であることを示す。次に、MPNN＋VNとDeepSetsの関係を活用することで、幅O(n^d)、深さO(1)のMPNN＋VNが、入力特徴次元dに対して、自己注意層を任意に精度良く近似可能であることを証明する。最後に、いくつかの仮定の下で、幅O(1)、深さO(n)のMPNN＋VNが、GTの自己注意層を任意の精度で近似可能である明示的な構成を提示する。実証的な観点からは、以下の3点を示す。1）MPNN＋VNは予想外に強力なベースラインであり、最近提案されたLong Range Graph Benchmark（LRGB）データセットにおいてGTを上回る性能を発揮する。2）我々のMPNN＋VNは、OGBデータセットの広範な範囲において、初期実装よりも優れた結果を達成する。3）気候モデリングタスクにおいて、MPNN＋VNはLinear Transformerおよび従来のMPNNを上回る性能を示す。