Graph Neural Networks are Heuristics

技術要約：グラフニューラルネットワークはヒューリスティックである

問題の定義
本論文は、ユークリッド型巡回セールスマン問題（TSP）を取り扱う。これは、$n$ 個の都市を通過する最短のハミルトン閉路を見つけることを目的とした、典型的な組合せ最適化問題である。著者らは、GNN（グラフニューラルネットワーク）が単なる補助的な役割（スコアの提供、探索の誘導、あるいは古典的なソルバーの模倣）に留まっているという従来のパラダイムに異議を唱える。代わりに、本論文は、GNNがスタンドアロンの学習されたヒューリスティックとして機能し得ることを提唱している。具体的な課題は、自己回帰的なデコーディング、強化学習の報酬、明示的な探索手順（ビームサーチなど）、あるいは事後的な局所改善（2-optなど）に頼ることなく、単一のフォワードパスで完全なツアーを構築することである。

手法
提案手法は、問題の幾何学的構造から直接TSPインスタンスを学習する、非自己回帰的かつ教師なしのGNNフレームワークである。

1. 目的関数と定式化:
   TSPは、距離行列 $D$ と、巡回シフト行列 $V$ によって変換された置換行列 $P$ の積のトレースを最小化するものとして定式化される。エンドツーエンドの勾配ベースの最適化を可能にするため、離散的な置換 $P$ は、学習中にGumbel-Sinkhorn緩和を用いてソフト置換行列 $T$ に緩和される。損失関数は単純に期待ツアー長である：$L_{TSP} = \langle D, TVT^\top \rangle$。推論時には、ソフト置換はハンガリアン法を用いてハードな置換へと変換される。

2. 対称性を考慮した特徴抽出:
   モデルがユークリッド群の対称性（置換および平行移動の不変性・等変性）を尊重することを保証するため、著者らは決定論的な特徴抽出器を導入している。

   • 平行移動不変性: 都市の座標は、平均を引くことによって中心化される。
   • 標準フレーム: 中心化された点の経験共分散行列の固有ベクトルを用いて、正規直交フレームが構築される。これにより、回転と反射の曖昧さが除去される。
   • 調和符号化: 点は、この標準フレーム上に投影され、固有の極座標（$r, \theta$）を導出する。角度情報は $M$ 個のフーリエ調和（$\sin(m\theta), \cos(m\theta)$）を用いてエンコードされ、GNNに回転不変な構造的手がかりを提供する。

3. ネットワークアーキテクチャ:
   コアモデルは、Scattering-Attention グラフニューラルネットワーク（SCT-GNN）である。これは、拡散ベースの表現（平滑化されたランダムウォーク行列の累乗から導出されたグラフ演算器を使用）と、異なる拡散スケール間で特徴を適応的に混合する学習可能なアテンションメカニズムを組み合わせたものである。ネットワークは、その構造上、置換等変である。

4. 多様性のためのアンサンブル戦略:
   複数のモデルを訓練したり反復的な探索を行ったりすることなく、解の多様性を生成するために、単一の学習プロセス内で2つのメカニズムを採用している。

   • モンテカルロ（MC）ドロップアウト: 推論時にドロップアウトが適用される。異なるドロップアウトマスクを用いて複数の確率的なフォワードパスを実行することで、単一の訓練済みインスタンスから多様なツアーを生成する。
   • スナップショット・アンサンブル: 単一の学習実行中の異なるエポックにおいて、複数のチェックポイントが保存される。これらのスナップショットは、最適化ランドスケープにおける異なる点を示しており、推論時に共同で使用される。スナップショットの中で最良のツアーが選択される。

主な貢献

• スタンドアロンのヒューリスティックとしてのGNN: 本論文は、GNNが補助的な探索や精緻化なしに、単一のフォワードパスで有効なツアーを生成する完全なヒューリスティックになり得ることを示している。
• 教師なし学習: モデルは、正解となる最適解や強化学習の報酬を必要とせず、ツアー長の最小化という目的のみによって学習を行う。
• グローバル構造の学習: 局所的な貪欲メカニズムを排除し、グローバルなハミルトン閉路の目的関数に依存することで、純粋に局所的な決定ルール（最近傍法など）が見落とす非局所的な組合せ制約を学習する。
• 効率性: 本手法はGPU上でミリ秒単位の推論を実現しており、自己回帰的なデコーディングや探索に依存する他の学習ベースのアプローチと比較して、優れた品質と効率のトレードオフを提供している。

結果
実験は、一様ユークリッド分布から抽出された $n=100, 200, 500$ のノードを持つTSPインスタンスに対して行われた。

• 貪欲法との比較: モデルは、貪欲な最近傍法（NN）のベースラインを一貫して上回った。TSP100において、平均ツアー長は9.67（貪欲法）から8.18（決定論的GNN）へと改善した。
• 古典的ヒューリスティックとの比較: 本手法は、小さなインスタンス（TSP100, TSP200）においてクリストフィード・アルゴリズムを大幅に上回り、TSP500では同等の性能を示したが、GPU上での推論時間は数桁小さい。
• 学習ベースのベースラインとの比較: 強化学習（RL）および教師あり学習（SL）のベースライン（例：GAT, GCN）と比較して、提案手法は競争力のある、あるいは優れた最適性ギャップ（例：ビームサーチを用いた強力なRLベースラインの2.48%に対し、TSP100で4.39%のギャップ）を達成しつつ、自己回帰的なデコーディングやビームサーチを回避することで大幅に高速化されている。
• アンサンブルの効果: MCドロップアウトとスナップショット・アンサンブルの両方が、最適性ギャップをさらに縮小させた。これら両方の戦略を組み合わせたものが最良の結果（TSP100で4.39%、TSP200で8.25%、TSP500で12.11%のギャップ）をもたらしたが、推論時間はミリ秒の範囲内（TSP500の結合アンサンブルで最大約82msまで）に留まった。

意義と主張
ヒューリスティックは、手作業で設計されたルールや探索手順である必要はなく、問題の構造から直接学習されることが可能であると本論文は主張している。TSPを直接的な置換学習と微分可能なハミルトン閉路目的関数として定式化することにより、著者らはGNNがグローバルな組合せ制約を内部化できることを示した。その意義は、組合せ最適化のパラダイムの転換にある。構造的制約と生成モデルが、難解な問題を解決するための基礎として、明示的な探索に取って代わり得るということである。結果は、「学習されたヒューリスティック」が、特に探索コストが禁止的な状況において、品質と計算効率の両面で古典的な設計手法に匹敵、あるいは凌駕し得ることを示唆している。本研究は、教師なしGNNを、組合せ最適化のための新しいクラスの高速な学習済みヒューリスティックとして位置づけている。