トランスフォーマーにおけるメッセージ伝達なしのグラフ誘導バイアス

グラフデータ向けのTransformerは、さまざまな学習タスクにおいてますます注目され、成功を収めつつある。グラフTransformerにおいて、グラフ固有の誘導的バイアス（inductive biases）は極めて重要であり、従来の研究ではメッセージパッシングモジュールや／または位置符号化（positional encodings）を用いてこれを導入している。しかし、メッセージパッシングを採用するグラフTransformerは、メッセージパッシングに起因する既知の問題を引き継ぐ一方で、他の分野で用いられるTransformerとは著しく異なるため、研究進展の転移が困難になる。一方、メッセージパッシングを用いないグラフTransformerは、小さなデータセットにおいては性能が劣りがちであり、その際には誘導的バイアスの重要性がより顕著になる。このギャップを埋めるために、本研究ではメッセージパッシングを一切用いない新たなグラフTransformer「Graph Inductive bias Transformer（GRIT）」を提案する。GRITは、それぞれ理論的・実証的に正当化された複数のアーキテクチャ的変更に基づいている。具体的には、ランダムウォーク確率で初期化された学習可能な相対的位置符号化、ノードおよびノードペアの表現を動的に更新する柔軟なアテンション機構、および各層に次数情報（degree information）を注入する仕組みを採用している。さらに、GRITが表現力を持つことを理論的に証明しており、最短経路距離やさまざまなグラフ伝搬行列を表現可能であることを示した。実験において、GRITは多様なグラフデータセットにおいて最先端の性能を達成し、メッセージパッシングを用いないグラフTransformerがもたらす潜在的な力の高さを示している。