グラフ変換器（Graph Transformers）は、さまざまなグラフ学習および表現学習タスクにおいて有望なアーキテクチャとして注目を集めています。しかし、その成功にもかかわらず、メッセージパッシングネットワークと同等の精度を維持しつつ、大規模なグラフにスケーラブルに拡張することは依然として困難な課題です。本論文では、強力かつスケーラブルなグラフ変換器を構築するためのフレームワーク「Exphormer」を提案します。Exphormerは、仮想グローバルノード（virtual global nodes）と拡張グラフ（expander graphs）の二つのメカニズムに基づくスパースアテンション機構から構成されており、これらのメカニズムの数学的特性（スペクトル拡張性、擬似乱数性、スパース性など）により、グラフサイズに対して計算量が線形に増加するグラフ変換器を実現しつつ、得られる変換器モデルの望ましい理論的性質を証明可能にしています。また、最近提案されたGraphGPSフレームワークにExphormerを組み込むことで、多様なグラフデータセットにおいて競争力のある実験結果が得られ、特に3つのデータセットで最先端の性能を達成しました。さらに、従来のグラフ変換器アーキテクチャよりも大規模なグラフデータセットへのスケーラビリティを示しました。コードは以下のURLから入手可能です：\url{https://github.com/hamed1375/Exphormer}。