A discrete Benamou-Brenier formulation of Optimal Transport on graphs

论文技术总结：图上的离散 Benamou-Brenier 最优输运公式

1. 研究背景与问题 (Problem)

• 背景：最优输运（Optimal Transport, OT）是衡量两个概率分布之间差异的核心工具。经典的 Kantorovich 公式将 OT 定义为耦合（coupling）上的最小化问题。Benamou-Brenier 公式则提供了一种动态视角，将 Wasserstein 距离 $W_p$ 表示为在时间依赖的分布流 $f_t$ 和速度场 $v_t$ 约束下的能量最小化问题，其中约束条件为连续性方程（输运方程）$\partial_t f + \nabla \cdot (f v) = 0$。
• 现有挑战：
  • 在连续空间（如 $\mathbb{R}^d$）中，Benamou-Brenier 公式非常成熟。
  • 在离散域（如图 $G=(V, E)$）上，直接应用连续公式并不适用，因为离散测度的插值（如 McCann 插值）可能会离开离散定义域进入连续空间。
  • 虽然 Erbar 和 Maas 提出了基于 $W_2$ 的离散类比，但该度量并非真正的 $W_2$ 距离。
  • 对于 $W_1$ 距离，虽然 Beckmann 公式提供了静态的边流形式，但缺乏一个包含时间参数的、类似于 Benamou-Brenier 的动态公式来描述 $W_1$ 测地线。
• 核心问题：如何在一般图上构建一个离散的输运方程，并推导出 $W_1$ 距离的 Benamou-Brenier 动态公式，进而分类图上的常数速度 $W_1$ 测地线？

2. 方法论 (Methodology)

作者提出了一套基于图论和离散微积分的框架，主要步骤如下：

• 离散输运方程的构建：

  • 引入关联矩阵 (Incidence Matrix) $\Omega$ 来定义图上的梯度 $\nabla$ 和散度 $\nabla \cdot$。
  • 定义了一个三元组 $(f, v, g)$，其中：
    • $f(t)$：定义在顶点 $V$ 上的概率分布路径。
    • $v(t)$：定义在边 $E$ 上的速度场。
    • $g(t)$：定义在边 $E$ 上的分布（作为速度的权重）。
  • 离散输运方程：$\partial_t f = \Omega \cdot (v \cdot g)$。
    • 这里 $v \cdot g$ 是边上的分量乘积。该方程表明节点上的质量变化率等于流入与流出该节点的通量差。
  • 与连续情况不同，在离散图中，速度 $v$ 和分布 $g$ 共同存在于边上，而非 $v$ 仅存在于顶点。

• 能量泛函定义：

  • 定义离散能量泛函 $I_q(v, g)$：
    $$I_q(v, g) = \left( \int_0^1 \sum_{k \in E} g_k(t) |v_k(t)|^q dt \right)^{1/q}$$
  • 定义离散距离 $V_q(f(0), f(1))$ 为满足输运方程的所有三元组 $(f, v, g)$ 中 $I_q$ 的下确界。

• 分步推导策略：

  1. 树 (Tree) 的情况：利用树的无环特性，通过定义“尾部分布”（Tail Distributions）$F_x$，将输运方程转化为可逆形式，从而精确求解。
  2. 一般图 (General Graph) 的情况：利用关联矩阵 $\Omega$ 的核空间（Cycle Space）性质，将问题转化为关于边流 $J = \int_0^1 vg dt$ 的优化问题，并与 Beckmann 公式建立联系。

3. 主要贡献与结果 (Key Contributions & Results)

• 定理 1：树上的 Benamou-Brenier 公式

  • 对于根树，证明了 $W_1(f(0), f(1)) = \inf \{ I_2(v, g) : \partial_t f = \Omega \cdot (vg) \}$。
  • 给出了常数速度解 (Constant Speed Solutions) 的显式构造：$v_k = \text{sign}(\partial_t F_{\lceil k \rceil}) |v|$，$g_k = |\partial_t F_{\lceil k \rceil}| / |v|$。
  • 证明了在该构造下，$I_2(v, g)$ 恰好等于 $W_1$ 距离，且 $f$ 是常数速度测地线。

• 定理 2：一般图上的 Benamou-Brenier 公式

  • 将结果推广到任意连通图。证明了对于任意 $q \ge 1$，有 $W_1(f(0), f(1)) = V_q(f(0), f(1))$。
  • 通过“简化公式”（Reduced Formulation），证明了最小化问题等价于寻找满足 $\Omega \cdot \int_0^1 gv dt = f(1) - f(0)$ 的边流，这直接联系了 Beckmann 公式。
  • 证明了存在常数速度解（即 $|v_k|$ 在时间和空间上均为常数）能达到最小值。

• 命题 4：测地线的分类 (Characterisation of Geodesics)

  • 核心发现：如果 $(v, g)$ 是达到 $W_1$ 最小值的常数速度解（即 $|v_k| = c$），则其诱导的路径 $f(t)$ 是常数速度 $W_1$ 测地线。
  • 逆向结论：任何常数速度 $W_1$ 测地线都可以由这样的 $(v, g)$ 诱导。
  • 推论 1 (凸插值是测地线)：线性插值 $f(t) = (1-t)f(0) + tf(1)$总是常数速度$W_1$ 测地线。
  • 非唯一性：除了线性插值，还存在其他非线性的常数速度测地线。例如，对于二项分布 $Bin(n, p)$，参数线性变化的路径$Bin(n, (1-t)p + tq)$ 也是测地线（见示例 3）。

4. 技术细节与关键洞察

• 尾部分布 (Tail Distributions)：在树上，作者利用尾部分布 $F_x = \sum_{y \in U(x)} f_y$ 将顶点上的输运方程转化为边上的简单代数关系 $\partial_t F_{\lceil k \rceil} = v_k g_k$。这是解决树结构问题的关键。
• 关联矩阵的逆与循环空间：在一般图上，$\Omega$ 不可逆。作者利用 $\Omega$ 的右逆和核空间（对应图的循环）来参数化解空间。这解释了为什么在一般图上解不唯一，以及如何通过调整循环分量来构造常数速度解。
• 与 Beckmann 公式的联系：通过积分 $\int_0^1 gv dt$，离散 Benamou-Brenier 公式自然地退化为静态的 Beckmann 公式（最小化 $\sum |J_k|$ 满足 $\Omega J = f(1)-f(0)$）。这证明了动态公式是静态公式的时间参数化推广。

5. 意义与影响 (Significance)

• 理论完整性：填补了离散最优输运理论中 $W_1$ 动态公式的空白。此前只有 $W_2$ 的离散类比（Erbar-Maas），而 $W_1$ 的 Benamou-Brenier 形式一直未解决。
• 测地线分类：明确分类了图上的常数速度测地线，揭示了测地线的不唯一性（既有线性插值，也有参数化插值）。这对于理解离散空间中的几何结构至关重要。
• 算法与应用潜力：
  • 该公式为在图数据（如社交网络、生物网络）上计算 Wasserstein 距离提供了新的优化视角。
  • 由于 $W_1$ 在机器学习中常作为损失函数（如 GANs），该离散动态公式可能为设计基于图结构的梯度流（Gradient Flows）或优化算法提供理论基础。
  • 示例中展示了二项分布和泊松分布在图上的插值，表明该方法适用于处理离散概率分布的演化问题。

总结：该论文成功地将连续空间中的 Benamou-Brenier 动态公式推广到了离散图结构上，特别是针对 $W_1$ 距离。通过引入边上的速度 - 分布对 $(v, g)$ 和关联矩阵，作者不仅建立了动态公式，还深入刻画了图上的测地线几何性质，为离散最优输运理论奠定了坚实基础。