論文「A discrete Benamou-Brenier formulation of Optimal Transport on graphs」の技術的サマリー

本論文は、グラフ上の離散空間における最適輸送（Optimal Transport）問題、特に Wasserstein-1 距離（$W_1$）の Benamou-Brenier 定式化を提案し、グラフ上の定速測地線（constant speed geodesics）を分類することを目的としています。連続空間における Benamou-Brenier 定式化の離散版を構築し、木構造（Tree）および一般の連結グラフ（Graph）に対してその有効性を証明しています。

以下に、問題設定、手法、主要な貢献、結果、および意義について詳細をまとめます。

1. 問題設定と背景

• 最適輸送と Wasserstein 距離: 古典的な最適輸送問題は、2 つの確率測度 $\mu, \nu$ を最小コストで変換する方法を問うものです。Kantorovich 定式化では、結合（coupling）の集合上でコストの最小値を求めます。
• Benamou-Brenier 定式化: 連続空間 $\mathbb{R}^d$ において、Benamou と Brenier はこの最小化問題を、時間依存する分布 $f_t$ と速度場 $v_t$ の対を用いた変分問題として再定式化しました。これは輸送方程式 $\partial_t f_t + \nabla \cdot (f_t v_t) = 0$ の制約下で、運動エネルギーの積分を最小化する問題として表現されます。
• 離散空間における課題: 離散空間（特にグラフ）では、測地線が連続空間に埋め込まれると定義域外に出てしまうため、単純な連続化は機能しません。また、$W_1$ 距離に対する Benamou-Brenier 型の時間依存定式化は、グラフ上で未解決の課題でした（$W_2$ については Erbar-Maas による定式化が存在しますが、これは Riemannian 構造を持つ別の距離です）。
• 既存研究: Hillion と Johnson は整数格子 $\mathbb{Z}$ 上で $W_1$ の離散 Benamou-Brenier 形式の十分条件を示しましたが、一般のグラフへの拡張は行われていませんでした。

2. 手法と提案する定式化

著者らは、グラフ上の新しい「離散輸送方程式」を提案し、これに基づいて Benamou-Brenier 型の定式化を導出しました。

2.1 離散輸送方程式の構築

連続方程式 $\partial_t f + \nabla \cdot (fv) = 0$ のアナロジーとして、以下の 3 つの要素からなる組 $(f, v, g)$ を定義します。

• $f(t)$: 頂点（vertices）上の確率分布の経路。
• $v(t)$: 辺（edges）上の速度関数。
• $g(t)$: 辺上の確率分布（質量の重み）。

定義 6（離散輸送方程式）:
グラフ $G=(V, E)$ とその接続行列（incidence matrix）$\Omega$ に対して、以下の方程式を満たすとき、輸送方程式が満たされると定義します。
$$\partial_t f(t) = \Omega \cdot (v(t) g(t))$$
ここで、$v(t)g(t)$ は成分ごとの積です。この式は、ノード $x$ における分布の変化率が、そのノードに流入・流出する辺上の「速度×分布」の正味の差（離散発散）によって記述されることを意味します。

2.2 目的関数（エネルギー汎関数）

Benamou-Brenier 定式化では、以下のエネルギー汎関数 $I_q$ を最小化します。
$$I_q(v, g) = \left( \int_0^1 \sum_{k \in E} g_k(t) |v_k(t)|^q dt \right)^{1/q}$$
特に $q=1$ の場合、これは $W_1$ 距離に対応します。

2.3 削減定式化（Reduced Formulation）

一般のグラフでは、$\Omega$ の逆行列が一意に定まらないため、$(v, g)$ を $f$ から直接一意に決定できません。著者らは、輸送方程式の解の構造を解析し、$(f, v, g)$ の探索を、辺上の $(v, g)$ の探索に帰着させる「削減定式化」を提案しました。
$$V_q(f(0), f(1)) = \inf_{v, g} \left\{ I_q(v, g) : f(1) - f(0) = \Omega \int_0^1 g(t)v(t) dt \right\}$$
これは、Beckmann 定式化（時間非依存）の時間依存版と見なせます。

3. 主要な結果と定理

3.1 木構造（Tree）上の結果

木グラフでは、根から枝方向へ矢印を向けることで「尾部分布（tail distribution）」$F_x$ を定義できます。

• 命題 2: 木上の $W_1$ 距離は、尾部分布の差の絶対値の和として閉形式で表せます（Evans の結果）。
• 定理 1: 木グラフにおいて、$W_1$ 距離は上記の Benamou-Brenier 定式化の最小値と一致します。
  $$W_1(f(0), f(1)) = \inf_{f, v, g} I_2(v, g)$$
  この最小値は、定速測地線によって達成され、その速度場は一定の大きさをもちます。

3.2 一般グラフ上の結果

• 定理 2（主定理）: 任意の連結グラフ $G$ および $q \ge 1$ に対して、$W_1$ 距離は Benamou-Brenier 定式化の最小値と一致します。
  $$W_1(f(0), f(1)) = \inf_{f, v, g} \left\{ \left( \int_0^1 \sum_{k \in E} g_k(t) |v_k(t)|^q dt \right)^{1/q} : \partial_t f = \Omega \cdot (vg) \right\}$$
  証明では、Beckmann 定式化との関係と、定速解への変換可能性（Lemma 3）を用いて、下限と上限が一致することを示しています。

3.3 測地線の分類

• 命題 4: 最小値を達成する $(v, g)$ 対（特に定速解）から誘導される経路 $f(t)$ は、$W_1$ 定速測地線となります。
• 系 1（凸補間）: 任意の 2 点 $f(0), f(1)$ に対して、線形補間 $f(t) = (1-t)f(0) + tf(1)$ は定速測地線となります。これは Beckmann 流の最小解が凸補間を与えることと対応します。
• 非一意性: 線形補間以外にも、二項分布やポアソン分布などの例（Example 3, 4）のように、非線形なパラメータ変化による定速測地線が存在することが示されました。

4. 意義と貢献

1. 理論的統一: 連続空間の Benamou-Brenier 定式化を、グラフという離散構造に自然に拡張しました。これにより、$W_1$ 距離の動的な解釈（時間発展する輸送過程）がグラフ上で確立されました。
2. 計算的可能性: 木構造や一般グラフにおいて、$W_1$ 距離を計算するための新しい変分問題（最適制御問題）を提供しました。これは、勾配流（Gradient Flows）や機械学習における損失関数としての応用可能性を秘めています。
3. 測地線の構造解明: グラフ上の $W_1$ 測地線が、単に線形補間だけでなく、特定の確率分布族（二項分布など）におけるパラメータの線形変化など、多様な形態を取り得ることを明らかにしました。
4. 既存研究の一般化: Hillion と Johnson の $\mathbb{Z}$ 上の結果を一般のグラフへ拡張し、木構造における尾部分布を用いた明示的な解を導出しました。

5. 結論

本論文は、グラフ上の最適輸送問題に対して、時間依存する輸送方程式とエネルギー汎関数を用いた Benamou-Brenier 定式化を確立しました。この定式化は $W_1$ 距離と等価であり、定速測地線の存在と性質を特徴づけます。この成果は、離散空間における最適輸送の理論的基盤を強化し、ネットワーク上のデータ分析や確率過程の解析への応用への道を開くものです。