曲率を用いたグラフ上のオーバー・スクァッシングおよびボトルネックの理解

多数のグラフニューラルネットワーク（GNN）は、メッセージパッシングという枠組みを採用しており、ノード特徴量が入力グラフ上で伝播される。近年の研究では、長距離相互作用に依存するタスクにおいて、メッセージパッシングの効率を制限する要因として、遠方ノードからの情報伝達における歪み（distortion）が指摘されている。この現象は「オーバー・スクワイジング（over-squashing）」と呼ばれており、$k$-ホップ近傍の数が$ k $とともに急速に増加するグラフのボトルネックに起因するものと、ヒューリスティックに説明されてきた。本研究では、GNNにおけるオーバー・スクワイジング現象を明確に定式化し、グラフ内のボトルネックがどのようにこの現象を引き起こすかを分析する。そのために、新たなエッジベースの組合せ的曲率を導入し、負の曲率を持つエッジがオーバー・スクワイジング問題の原因であることを証明する。さらに、この曲率に基づくグラフ再接続（rewiring）手法を提案し、実験的にその有効性を検証した。