グラフトランスフォーマーに対するk最大内積注意とGraphGPSの表現力

Abstract

グラフ・トランスフォーマーは、オーバースクワッシングや長距離依存のモデリングが難しいといった従来のグラフニューラルネットワークの限界を克服するうえで有望であることが示されてきました。しかし、大規模グラフへの適用は、すべて対すべて（all-to-all）注意機構による二次的なメモリおよび計算複雑性によって妨げられています。線形化された注意や、注意のパターンを制限するような代替案が提案されているものの、これらはしばしば性能を低下させたり、表現力を制限したりします。効率と有効性のより良い両立を図るために、グラフ・トランスフォーマーのためのk最大内積（k-Maximum Inner Product: k-MIP）注意を提案します。k-MIP注意は、トップk演算によって、クエリごとに最も関連性の高いキー・ノードを選択し、疎でありながら柔軟な注意パターンを得ます。さらに、記号行列に基づく注意スコアの計算と組み合わせることで、メモリの計算量を線形にし、すべて対すべての注意と比較して最大で1桁（オーダー）の実用的な高速化を実現します。これにより、単一のA100 GPUで50万ノードを超えるグラフの処理が可能になります。加えて、k-MIP注意がグラフ・トランスフォーマーの表現力を損なわないことを示す理論的分析を行い、具体的には、k-MIPトランスフォーマーが任意の精度で任意のフル注意（full-attention）トランスフォーマーを近似できることを証明します。さらに、我々の注意機構を組み込むGraphGPSフレームワークの表現力を分析し、S-SEG-WLテストに基づいてそのグラフ識別能力の上限を確立します。最後に、Long Range Graph Benchmark、City-Networksベンチマーク、ならびに2つのカスタムな大規模インダクティブ点群データセットにおいて、我々のアプローチを検証し、スケーラブルなグラフ・トランスフォーマーの中で一貫して上位の成績を収めることを示します。