グラフニューラルネットワークにおけるノード減少プーリングを用いた階層的表現学習

グラフニューラルネットワーク（GNN）において、プーリング演算子は入力グラフの局所的な要約を計算し、そのグローバルな性質を捉える役割を果たしており、階層的な表現を学習する深層GNNを構築する上で基盤的な要素である。本研究では、グラフの全体的なトポロジーを保持しつつ、より粗いグラフを生成するためのGNN用プーリング演算子である「ノードデシメーションプーリング（NDP）」を提案する。学習過程において、GNNは新しいノード表現を学習し、事前にオフラインで計算された粗化グラフのピラミッドに適合させる。NDPは以下の3段階から構成される。まず、スペクトルアルゴリズムを用いて\maxcut{}解の近似として得られたグラフの分割の一方の側に属するノードを選択する「ノードデシメーション」プロセスを実施する。次に、選択されたノードをKron縮約（Kron reduction）により接続し、粗化されたグラフを構築する。最後に、得られたグラフは非常に密な構造となるため、計算コストを低減するために、粗化されたグラフの隣接行列に対してスパース化手順を適用する。特に、グラフ構造に顕著な影響を与えることなく多数の辺を削除可能であることを示している。実験結果から、NDPは最先端のグラフプーリング演算子と比較してより効率的であり、同時に多様なグラフ分類タスクにおいて競争力のある性能を達成していることが明らかになった。