グラフへのViT/MLP-Mixerの一般化

グラフニューラルネットワーク（GNN）は、グラフ表現学習分野において大きな可能性を示している。従来のGNNは、複数の層を積み重ねることで、グラフ全体にわたって情報を伝達する局所的なメッセージパッシング機構を定義している。しかし、このアーキテクチャは「過剰圧縮（over-squashing）」および「長距離依存関係の劣化」という2つの主要な制約に直面しており、これらを解決するためにはグローバルアテンションを用いる必要があるが、その場合計算コストが二次関数的（quadratic）に増加するという問題がある。本研究では、コンピュータビジョン分野で提案されたViT/MLP-Mixerアーキテクチャを活用することで、これらの構造的制約を克服する代替手法を提案する。我々は、新しいGNNクラスである「Graph ViT/MLP-Mixer」を導入し、以下の3つの重要な特性を持つ。第一に、Long Range Graph BenchmarkおよびTreeNeighbourMatchデータセットを用いた実験により、長距離依存関係を効果的に捉え、過剰圧縮の問題を緩和できることを示した。第二に、ノード数およびエッジ数に対して線形の計算複雑度を持つため、関連するGraph Transformerや表現力の高いGNNモデルと比較して、より優れた速度およびメモリ効率を実現した。第三に、グラフ同型性の表現力において高い性能を発揮し、少なくとも3-WL（Weisfeiler-Lehman）非同型グラフを区別可能であることを確認した。本アーキテクチャは、4つのシミュレーションデータセットおよび7つの実世界ベンチマークにおいて評価され、すべてのタスクで競争力のある結果を示した。実装コードは再現性を確保するために以下より公開されている：\url{https://github.com/XiaoxinHe/Graph-ViT-MLPMixer}。