GAP: 一般化近似グラフ分割フレームワーク

グラフ分割とは、グラフのノードをバランスの取れたパーティションに分割しつつ、パーティション間のエッジカットを最小限に抑える問題です。この組合せ的な性質から、多段階手法やスペクトラルクラスタリングの変種など、多くの近似解法が開発されてきました。本研究では、深層学習アプローチを用いたグラフ分割のための汎用的な近似フレームワークであるGAP（Generalizable Approximate Partitioning）を提案します。我々は分割目標を表す微分可能な損失関数を定義し、バックプロパゲーションを使用してネットワークパラメータを最適化します。各グラフに対して最適化を再実行するベースラインとは異なり、GAPは汎化能力を持っています。これにより、訓練時に見たことのないグラフでも推論時に高性能なパーティションを作成できるモデルを訓練することが可能となります。さらに、グラフの表現と分割損失関数の最適化を同時に行うことで、GAPは様々なグラフ構造に対して簡単に調整できます。我々はGAPの性能評価として、異なるサイズと構造を持つグラフ（例えばResNet, VGG, Inception-V3などの広く使用されている機械学習モデルのグラフ、スケールフリー・グラフ、ランダム・グラフ）を使用しました。結果として、GAPはベースラインと比較して最大100倍速いながら競争力のあるパーティションを達成し、見たことのないグラフにも汎化することが示されました。