要約
本稿では、ドット積アテンション（Vaswaniら、2017）の計算およびメモリ効率に優れた変種である低ランクグローバルアテンション（Low-Rank Global Attention: LRGA）モジュールをグラフニューラルネットワーク（GNN）に組み込むことの有効性を提唱する。このモジュールの導入によりGNNの一般化性能が向上することを理論的に定量化するため、表現力に優れた特定のGNNクラスに着目し、LRGAモジュールを追加することで、強力なグラフ同型性テストである2-Folklore Weisfeiler-Lehman（2-FWL）アルゴリズムとアルゴリズム的整合性をもたらすことを示す。具体的には、以下の3点を主張する：（i）最近のランダムグラフニューラルネットワーク（Random Graph Neural Network: RGNN）（Satoら、2020）フレームワークを検討し、それが確率的意味での普遍性（universality in probability）を持つことを証明する；（ii）LRGAを備えたRGNNが多項式カーネルを用いて2-FWLの更新ステップと一致することを示す；（iii）ランダムに初期化された2層MLPによって学習されたカーネル特徴写像のサンプル複雑度（sample complexity）を評価する。実用的な観点からは、既存のGNN層にLRGAモジュールを追加することで、現在のGNNベンチマークにおいて最先端の性能を達成する。最後に、さまざまなGNNアーキテクチャにLRGAを導入すると、異なるモデル間の性能ギャップがしばしば縮小されることが観察された。