一般化、強力でスケーラブルなグラフトランスフォーマーのレシピ

私たちは、線形複雑さを持つ一般的で強力かつスケーラブル（GPS）なグラフトランスフォーマーの構築方法と、多様なベンチマークにおいて最先端の結果を達成するレシピを提案します。グラフトランスフォーマー（GTs）は、最近の多くの論文によってグラフ表現学習の分野で注目を集めていますが、良い位置情報または構造情報のエンコーディングとは何か、それらがどのように異なるのかについて共通の基礎が欠けています。本論文では、異なる種類のエンコーディングをより明確な定義で要約し、$\textit{局所的}$、$\textit{全体的}$、または$\textit{相対的}$に分類します。従来のGTsは数百ノード程度の小さなグラフに制限されていましたが、ここでは局所的な実際のエッジ集約と完全接続型トランスフォーマーを分離することで、ノード数とエッジ数に対して線形複雑さ$O(N+E)$を持つ最初のアーキテクチャを提案します。私たちはこの分離が表現力に悪影響を与えないことを主張し、私たちのアーキテクチャはグラフ上の普遍関数近似器であることを示しています。私たちのGPSレシピには3つの主要な要素を選択することから始まります：(i) 位置情報/構造情報エンコーディング、(ii) 局所メッセージ伝播メカニズム、(iii) 全体注意メカニズム。私たちはこれらのエンコーディングをサポートし、小さなグラフでも大きなグラフでも効率性とスケーラビリティを提供するモジュール式フレームワーク$\textit{GraphGPS}$を提供します。私たちは16つのベンチマークでアーキテクチャをテストし、すべてにおいて非常に競争力のある結果を得ました。これにより、モジュール性と異なる戦略の組み合わせによって得られる経験的な利点が示されています。