AGDN: Learning to Solve Traveling Salesman Problem with Anisotropic Graph Diffusion Network

技術要約：AGDN – 非等方性グラフ拡散ネットワークを用いた巡回セールスマン問題の解決学習

問題定義
巡回セールスマン問題（TSP）は、一連の都市を正確に一度ずつ訪問し、出発点に戻る最短ルートを見つけることを目的とした、基本的な組合せ最適化問題である。グラフニューラルネットワーク（GNN）は、その問題のトポロジー的な探索空間との整合性から、TSPに対する効果的なツールとして台頭しているが、現在の学習ベースのアプローチには、以下の2つの決定的な限界が存在する：

1. 情報量の多いトポロジー的事前知識の欠如： 標準的なグラフ学習タスクとは異なり、TSPのインスタンスは通常、完全グラフとしてモデル化される。この構造には、最適解に関する固有のトポロジー的事前知識が存在しないため、モデルが解に関連する情報とノイズを区別することを困難にしている。
2. 疎性化による情報の損失： 計算量を管理するために、既存の手法ではTSPグラフを（$k$-NNなどを用いて）疎性化することが多い。しかし、このプロセスは最適解の一部となるエッジを取り除いてしまうリスクがある。最適なノードペアが切断された場合、浅いGNNは必要なマルチホップの関係を捉えることができず、一方で深いGNNはオーバースムーシング（過度な平滑化）やオーバースクワッシング（情報の圧搾）に苦しむことになる。

手法：非等方性グラフ拡散ネットワーク（AGDN）
著者らは、グラフの疎性化に依存せずにTSPを解決するために設計されたフレームワークであるAGDNを提案する。この手法は、以下の4つのコアコンポーネントで構成される：

1. MixScore 遷移行列：
   標準的な隣接行列や単純な距離ベースの遷移を用いる代わりに、AGDNはMixScore遷移行列を構築する。この行列は、2種類の情報を統合している：

   • ペアワイズ距離： 幾何学的な近接性を捉えるために、ガウスカーネル（$\exp(-e_{ij}/\sigma)$）を通じてエンコードされる。
   • ノード類似度： 2つの異なる潜在空間、すなわちソース（$S$）空間とデスティネーション（$D$）空間におけるノード埋め込みから導出される。
     この行列は、埋め込みの（$H_S H_D^T$）と正規化された距離行列（$T_{rw}$）を結合し、多層パーセプトロン（MLP）で処理することで定式化される。これにより、モデルは幾何学的距離と学習された構造的類似性の両方を反映した遷移確率をエンコードすることが可能になる。

2. 非等方性グラフ拡散：
   AGDNは、情報を受け取る方向（$S$）と送り出す方向（$D$）の両方に対して個別に情報を伝播させる拡散メカニメントを採用している。

   • マルチホップ・アテンション： 本フレームワークは、単一の畳み込み層内で$K$ホップ分の情報を集約するための、学習可能なマルチホップ・アテンション（パラメータ $\theta_k$ によって制御）を利用する。これにより、層を積み重ねる必要がなくなり、オーバースムーシングを軽減できる。
   • 非等方性（Anisotropy）： $S$空間と$D$空間を別々に維持することで、モデルは方向性のある情報の流れを捉え、ノードの特徴付けの粒度を高める。

3. ノード情報の集約：
   拡散後、$S$空間と$D$空間の埋め込みが集約される。著者らは、$S$空間の埋め込みをクエリ（Query）とし、$D$空間の埋め込みをキー（Key）およびバリュー（Value）とする自己注意（Self-attention）メカニズムを使用している。この非対称な集約に続いて、最終的なMLPによって統一されたノード埋め込みが生成される。

4. 解の特定：
   集約されたノード埋め込みは、外積を通じてエッジ埋め込みを生成するために使用される。エッジレベルのアテンションメカニズムがこれらの埋め込みを再重み付けし、重要なエッジを強調する。最終的に、MLPが各エッジが最適ツアーの一部である確率を表すヒートマップを予測する。このヒートマップは、最終的な解を構築するためのモンテカルロ木探索（MCTS）をガイドする。モデルは、教師あり学習（正解のヒートマップに対するクロスエントロピー）または教師なし学習（期待ツアー長の最小化）のいずれかを用いて最適化される。

主な貢献

• 問題の特性化： 本論文は、現在のGNNアプローチの限界、特にグラフの疎性化による切断と、完全グラフにおける情報量の多い事前知識の欠如を特定し、定式化した。
• アルゴリズム設計： MixScore遷移行列と非等方性グラフ拡散メカニズムの導入。これらの革新により、疎性化を行うことなく効率的なマルチホップ情報の伝播が可能になり、最適なノードペア間の接続性が保持される。
• 実証的検証： 広範な実験により、AGDNが様々な問題サイズおよびノード分布において、教師あり学習および教師なし学習の両方の設定で、最先端の手法を凌駕することを実証した。

実験結果
著者らは、200から1000ノードの範囲のTSPインスタンス、およびTSPLIBからの実世界のデータセットを用いてAGDNを評価した。

• 有効性： 教師あり学習（SL）の設定において、AGDNはGatedGCN、Att-GCN、DIFUSCOといったベースラインと比較して、最適解に対するギャップが最も低かった。例えば、TSP-1000において、GatedGCNのギャップが7.26%であったのに対し、AGDNは1.28%を達成した。教師なし学習（UL）においても、AGDNはUTSPおよびPositionを上回った。
• 効率性： AGDNは優れた計算効率を示した。特に、情報集約のホップ数が増加しても、GatedGCNよりも少ないパラメータ数と短い推論時間で済んだ。これは、単一の層でマルチホップ情報を捉える能力によるものである。
• 汎用性： モデルは、TSP-100で学習し、より大きなインスタンス（TSP-200, 500, 1000）や多様なノード分布（Uniform, Cluster, Explosion, Implosion）でテストした場合でも、強固な汎用性を示した。また、再学習なしで実世界のTSPLIBインスタンス（tsp225, pcb442, pr1002）に対しても高い性能を維持した。

意義
本論文は、AGDNがTSP解決における「グラフの疎性化」と「情報の損失」の間の根本的なトレードオフに対処していると主張している。非等方性拡散戦略とMixScore事前知識を導入することで、本フレームワークはGNNがTSPグラフの全結合性を効果的に活用することを可能にする。結果は、AGDNが理論的なグラフ学習能力と組合せ最適化の実践的な要求との間の溝を埋め、競争力のある推論時間を維持しながら、最先端の性能を達成するスケーラブルで汎用性の高いソリューションを提供することを示唆している。