技術的概要：有界種数グラフのための GenusSink アルゴリズム

問題定義

本論文は、最短経路距離をコスト関数として用いた有界種数グラフ（平面グラフや 3D 物体を近似するメッシュを含む）における**最適輸送（OT）**問題の解決に伴う計算上のボトルネックに対処するものである。

OT に対する標準的なアプローチ、例えば（エントロピー正則化を用いた）Sinkhorn アルゴリズムなどは、通常、以下の要件を伴う：

1. コスト行列 $C$（または一般化された距離行列 $K^\epsilon_f$）を完全に具体化するために、二次時間および二次空間を要する。ここで $C_{ij}$ はノード $i$ と $j$ 間のコストを表す。
2. 力尽き（brute-force）の線形計画法による解法には三次時間を要する。

Sinkhorn 反復法は輸送計画の発見における計算複雑性を二次時間 $O(n^2)$ に低減するが、それでも $n \times n$ の行列の保存と操作を必要とする。機械学習において一般的に用いられる大規模グラフ（3D メッシュ、道路ネットワークなど）の場合、この二次のメモリおよび時間要件は実行不可能となる。既存の効率的な近似手法（Greenkhorn、Screenkhorn、Nyström 法など）は、多くの場合、精度を犠牲にするか、低トレewidth ドメインのような特定のグラフ構造に対する正確な計算を提供できない。

核心的な課題は、コストが測地線（最短経路）距離によって定義されるグラフに対して、前処理、反復ステップ、および輸送計画の照会において準線形時間を達成し、かつ準線形メモリと高い精度を維持するアルゴリズムを設計することである。

手法：GenusSink

著者らは、近似一般化 Sinkhorn アルゴリズムの新しいクラスであるGenusSinkを提案する。この手法は以下の 3 つの主要な柱に依存している：

1. セパレーターに基づく分解とトレewidth

このアルゴリズムは、有界種数グラフの構造的性質を利用する。

• トレewidth 近似: 有界種数グラフ（平面グラフなど）は本質的に低いトレewidth を持たない（しばしば $O(\sqrt{n})$）が、最近の理論的結果 [14] は、それらの計量が低いトレewidth（$O(\log \log n)$）を持つグラフ上の計量によって正確に近似可能であることを示している。
• 木分解: GenusSink は、グラフ（または低いトレewidth の代理）の木分解を利用して、分割統治戦略を促進する。グラフは、バランスの取れたセパレーター（グラフをほぼ等しい成分に分割する頂点の集合）を用いて再帰的に分割される。

2. 分離グラフ場積分器（S-GFI）

一般化された距離行列 $D^\epsilon_f = [f_\epsilon(d_{i,j})]$ による行列 - ベクトル積を効率的に計算するための新しいデータ構造、**Separation Graph Field Integrator（S-GFI）**が導入される。

• 構造: S-GFI は、ノードがバランスの取れたセパレーターに対応する二分木である。各ノードは、セパレーターと部分グラフ成分（左側および右側）間の距離行列を含むメタデータを保存する。
• 統合プロセス: $y = D^\epsilon_f x$ を計算するために、アルゴリズムは木をトラバースする。セパレーター $S$ と成分 $A$ および $B$ を持つ与えられたノードに対して、$S$ を横断する経路からの寄与を計算する。
• 交差計算: 核心的な効率化は、cross_compute プロシージャから得られる。$A$ と $B$ 間のすべてのペア相互作用を明示的に計算する代わりに、以下を利用する：
  • 計算幾何学: 不等式制約を効率的に処理するために、距離のベクトルをソートする。
  • フーリエ解析と低変位ランク: 一般化された関数 $f$ に対して、論文は**心ある関数（cordial functions）**の理論と低変位ランク行列（特にコーシー型行列）の理論を活用し、準線形時間の乗算を行う。標準的な指数カーネル（$f(x) = e^{-x}$）の場合、その構造により、正確な $O(|A| + |B|)$ の更新が可能となる。
• 計算量: integrate 関数は $O(n \cdot \text{poly}(|S|) \cdot \log^{\text{poly}(|S|)}(n))$ で実行される。トレewidth が $O(\log \log n)$ のグラフの場合、全体の構築および反復時間は $n$ に対して準線形である。

3. 有界種数への実用的な実装

一般的な有界種数グラフに対する完全な低いトレewidth 埋め込みの構築は複雑になり得るため、著者らは実用的なヒューリスティックを提案する：

• 完全な理論的埋め込みの代わりに、$O(\sqrt{n})$ サイズのバランスの取れたセパレーターを見つける線形時間アルゴリズムを使用する。
• セパレーターをサブサンプリングし（$O(\log \log n)$ 点を保持）、残りを子ノードに分配する。
• S-GFI 木の深さはハイパーパラメータとして扱われ、漸近的な速度と、小さな部分グラフに対する力尽き行列 - ベクトル乗算の使用との間のトレードオフを可能にする。

主要な貢献

1. GenusSink アルゴリズム: 測地線コストを持つ有界種数グラフ上の OT に対して、準線形時間の前処理、反復、および照会を提供する新しいアルゴリズム的枠組み。
2. S-GFI データ構造: セパレーターに基づく分解と計算幾何学を活用することで、一般化された距離行列による効率的な行列 - ベクトル積を可能にする新しいデータ構造。
3. 理論的保証:
   • トレewidth が $O(\log \log n)$ のグラフ（例：木）において、GenusSink が力尽き測地線 Sinkhorn アルゴリズムと数値的に同等であることを証明。
   • 有界種数計量が加法的歪みを持つ低いトレewidth の代理によって近似可能であることを示し、平面および有界種数メッシュへのアルゴリズムの適用を可能にする。
4. 実証的検証: GenusSink が高密度測地線ベースラインと同等の精度を達成しつつ、大幅な高速化を提供することを示す広範な実験。

実験結果

本論文は、合成データセットおよび実世界データセット上で GenusSink を評価する：

• 合成擬似種数曲面: さまざまな「擬似種数」（複雑なトポロジーをシミュレート）を持つ平面グラフにおいて、GenusSink は数値精度まで高密度測地線フルカーネルベースラインと一致する。対照的に、他の効率的な手法（Greenkhorn、Screenkhorn、疎な Sinkhorn、Nyström）は顕著な精度のギャップを示す。GenusSink は、ノード数が増加するにつれて（最大約 20,000 ノードまで）、力尽きベースラインよりも著しく速くスケーリングする。
• Thingi10K メッシュ: 実世界の 3D メッシュ（最大 13k 頂点）に適用した場合、GenusSink は高密度測地線 Sinkhorn と比較して本質的に正確なままであり、他の近似手法は明らかな誤差を示す。
• 実世界応用（救急車配置の最適化）: ブロンクス（33k ノード）における救急車配置の最適化に関するケーススタディにおいて、GenusSink は、より低い平均応答時間（12.5 分対ベースラインの 13.4–14.5 分）を生み出し、応答時間の上部テール（95 パーセンタイル以上）において著しく優れた性能を示した。

意義と主張

本論文は、GenusSink が非ユークリッド領域における最適輸送の計算効率と数値精度の間のギャップを埋める重要な進歩であると主張する。

• 精度: 誤差を導入するスパース化や低ランク近似に依存する他の「効率的な」Sinkhorn 変種とは異なり、GenusSink は桁違いに高精度な計算を提供し、特定のグラフクラスに対して力尽き測地線解と事実上一致する。
• 効率性: 完全なコスト行列の具体化を必要とする標準的な Sinkhorn 実装の二次のボトルネックを克服し、準線形時間の計算複雑性を達成する。
• 汎用性: このアプローチは任意の有界種数グラフに適用可能であり、3D メッシュ処理、道路ネットワーク、および測地線距離が自然なコスト指標となる多様体学習タスクに適している。

著者らは、この手法が現在、有界種数グラフに限定されているが、将来的にはマイナーフリーグラフへの拡張を計画していると述べている。また、アルゴリズムは、トレewidth が小さい、または小さなトレewidth 構造によってよく近似できるグラフに対して特に効果的であることを強調している。