技術要約：ニューラル最適輸送によるメトリックグラフ上の生成モデリング

問題提起

道路ネットワーク、血管構造、河川系などの多くの科学的および幾何学的データセットは、自然にメトリックグラフ上に支持されています。メトリックグラフとは、エッジが長さを持ち、連続的な区間として扱われる一次元の測地空間です。既存の生成モデリング手法は、根本的な限界に直面しています。標準的な手法は、アンビエントなユークリッド空間内の点を生成するため、サンプルがグラフ上に支持されていることを保証したり、グラフ固有の計量幾何学を尊重したりすることができません。

逆に、グラフに対する従来の最適輸送（OT）アプローチは、多くの場合、有限のノードベースの測量で連続分布を近似する離散化に依存しています。このアプローチは計算上は容易ですが、離散化を精緻化するにつれてメッシュ依存の近似が生じ、元の領域の連続性を失うという課題があります。

本論文は、幾何学的な忠実度を損なうことなく、滑らかなアンビエント構造を計算に活用できる、連続的なグラフ支持型の生成フレームワークの必要性に対処しています。

手法

著者らは、メトリックグラフを滑らかなアンビエント空間に埋め込み、そこでエントロピー的OT問題を解き、サンプルをグラフへと投影するディープ生成モデリングフレームワークを提案しています。パイプラインは主に以下の3つのステージで構成されます。

1. 埋め込み (Embedding): メトリックグラフ $\Gamma$ を、写像 $\Psi$ を通じて滑らかなアンビエント多様体 $M_\Psi$ に埋め込みます。本論文では、2つの特定の埋め込みを調査しています。

   • 外的なユークリッド実現 ($\iota$): グラフを $\mathbb{R}^m$ に写します（例：道路ネットワークの平面座標）。
   • 内的なトロピカル・アベル・ヤコビ埋め込み ($\Phi_p$): グラフをそのトロピカル・ヤコビ・トーラス $J(\Gamma)$ に写します。この埋め込みはエッジの長さとサイクル構造のみに依存し、特定のユークリッド的な描画から独立した固有の幾何学を提供します。

2. ニューラル・エントロピック最適輸送 (Neural Entropic Optimal Transport):

   • ソース（$P_\Gamma$）とターゲット（$Q_\Gamma$）の測度は、アンビエント空間（$P_\Psi, Q_\Psi$）へと押し出されます（push-forward）。
   • ニューラル半双対パラメータ化を用いて、これら埋め込まれた測度間のエントロピー的カントロヴィッチ問題を解きます。
   • マップベースのモンジュ定式化とは異なり、このアプローチは結合（プラン）を学習します。ターゲット側のシュレディンガー・ポテンシャルは、ニューラルネットワーク $g_\theta$ によってパラメータ化されます。
   • ターゲットの原子に限定されたサンプルではなく連続的な出力を生成するために、学習された条件付き法則はアンビエント熱核 (heat kernel) を用いて平滑化されます。これにより、アンビエント空間内に存在する可能性のある（埋め込まれたグラフから外れた）サンプルが生成されます。

3. 復元 (投影–プルバック / Recovery: Projection–Pullback):

   • 熱平滑化されたサンプルは埋め込まれたグラフから外れる可能性があるため、埋め込まれたグラフ $\Psi(\Gamma)$ への最近接点投影 (nearest-point projection) が行われます。
   • その後、逆埋め込み $\Psi^{-1}$ を適用して、投影された点を元のメトリックグラフ $\Gamma$ へと写します。
   • 最終的な生成器は $\rho_\Gamma^\Psi = \Psi^{-1} \circ \text{proj}_{\Psi(\Gamma)}$ として構築され、生成されたすべてのサンプルが厳密に元のグラフ上に支持されることを保証します。

主な貢献

1. メトリックグラフのための初のディープ生成フレームワーク: 著者らの知る限り、コンパクトなメトリックグラフ上に連続的に支持された確率分布のための、初のディープ生成モデルを導入しました。
2. 二つのデュアル埋め込み幾何学: 本フレームワークは、以下の2つの異なる輸送幾何学に対して開発されました。
   • 外的なユークリッド実現。
   • ヤコビ・トーラスへの内的なトロピカル・アベル・ヤコビ埋め込み。
3. 理論的収束性: ニューラルネットワークの表現力が増大し、かつ熱スケールが消失するという同時極限において、学習された熱平滑化投影–プルバック生成器が、元のグラフ測度間の有効な輸送結合へと弱収束することを証明しました。これにより、アンビエント空間で学習しているにもかかわらず、極限の対象がグラフ上の正当な結合であることが保証されます。
4. ブリッジの処理: グラフ内のブリッジ（橋）を扱うために、標準的な拡張（仮想的な平行エッジの追加）を含んでいます。これにより、トロピカル・アベル・ヤコビ写像が単射であり続け、グラフがその像から復元できることを保証します。

実験結果

本手法は、合成ベンチマークおよび実世界のデータを用いて評価されました。

• 合成ベンチマーク: シータ、ホイール、グリッド、および小さな道路グラフを用いてテストされました。ニューラルOTのバリアント（トロピカルおよびユークリッドの両方）は、離散グラフOTに基づくヒューリスティックなベースライン（ノード補間およびアンビエント押し出し）と比較して、一貫して誤差を減少させました（固有のグラフ・ワッサースタイン距離 $W_1^\Gamma, W_2^\Gamma$ および密度/累積分布関数 $L_1$ 誤差の観点から）。2つの埋め込み幾何学は同等の性能を示しており、これは主要な利点が特定の埋め込みの優位性ではなく、償還されたエントロピー的輸送則にあることを示唆しています。
• スケーラビリティ: ニューラルなアプローチは、サポートサイズに対して良好にスケールします。大規模なサポートペアに対して固有の最短経路距離を評価する必要がある明示的なペアワイズ・グラフOT手法とは異なり、ニューラル手法はミニバッチで学習を行い、学習された規則をバッチ推論を通じて適用します。
• 実世界への応用: 本フレームワークは、ニューヨーク市マンハッタンにおける100万件のUber乗車地点に適用されました。
  • タスクは、グラフ支持型の空間密度生成（一様な道路ソースから乗車地点を生成することを学習する）です。
  • 高密度なグラフOTのベースラインは、メモリ制約（$10^{12}$ のペアワイズ・コスト）により実行不可能でした。
  • ニューラル・ユークリッド（グロモフ）モデルは、マンハッタンの道路グラフ上の主要な乗車構造を回収するサンプルを生成することに成功し、サブサンプリングされた部分集合（16,384点）で訓練されたヒューリスティックなベースラインを上回りました。

意義と主張

本論文は、離散化の弊害を回避し、メトリックグラフ上の確率分布のための原理的な解決策を提供することを目的としています。滑らかなアンビエント空間で輸送問題を解き、投影を介してグラフ支持型のサンプルを復元することで、本手法はドメインの連続的な幾何学を保持します。

著者らは、本アプローチがマップベースではなくプランベースであることを強調しており、これにより、それらをアンビエントな密度へと滑らかにすることなく、グラフ上の特異な測度を扱うことが可能になります。有効な結合への弱収束という理論的保証は、この手法が単なるヒューリスティックではなく、最適輸送理論に厳密な基礎を持っていることを保証しています。

本研究は、ニューラルOTが非ユークリッドの一次元幾何学的ドメインに適応可能であることを示しており、都市モビリティから生物学的ネットワークに至るまでの幅広いアプリケーションに対して、離散的なグラフOTに代わるスケーラブルな選択肢を提供します。著者らは、収束証明の漸近的な性質（有限サンプル率の欠如）や、現在の焦点が条件付き予測ではなく無条件生成にあることなどの限界についても言及しています。