グラフニューラルネットワークにおけるオーバースムージングとオーバースキッシングのための最適グラフ書き換えの複雑性について

Abstract

グラフニューラルネットワーク（GNN）は、深いアーキテクチャへスケールさせる際に2つの根本的な課題に直面する。すなわち、ノード表現が区別できないベクトルへ収束してしまう「過剰平滑化（oversmoothing）」と、遠くのノードからの情報がボトルネックを通じて伝播できない「過剰圧縮（oversquashing）」である。これら2つの現象は基盤となるグラフ構造と密接に結び付いており、自然な問いとして「これらの問題を軽減するためにグラフトポロジーを最適化できるのか？」が挙げられる。本論文は、そのようなグラフ構造最適化の計算複雑性に関する理論的な検討を提供する。過剰平滑化と過剰圧縮の緩和を、それぞれスペクトルギャップとコンダクタンスに基づくグラフ最適化問題として定式化する。いずれの問題についても、Minimum Bisection からの縮約により、厳密な最適化がNP困難であることを証明し、判定版のNP完全性を確立する。我々の結果は、GNN最適化のためのグラフ配線（rewiring）における基本的な限界を理解するための理論的基盤を与え、実務において近似アルゴリズムやヒューリスティック手法を用いることを正当化する。