🤖 AI

Your GFlowNet Secretly Learns an Optimal Transport Plan

本文建立了非无环生成流网络（GFlowNets）与最优传输之间的理论联系，证明了在最小流 GFlowNet 中固定初始流分布会将其目标函数转化为一个 Kantorovich 最优传输问题，从而使该网络能够在大型图上学习并采样最优传输计划。

原作者： Ian Maksimov, Nikita Morozov, Denis Belomestny, Sergey Samsonov

发布于 2026-06-05

📖 1 分钟阅读☕ 轻松阅读

原作者： Ian Maksimov, Nikita Morozov, Denis Belomestny, Sergey Samsonov

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你是一家规模宏大、混乱不堪的快递公司的经理。你的仓库里堆满了包裹（源点），需要送到城市中的各个住户手中（目标点）。这座城市就像一个巨大的网格或复杂的迷宫，你希望用绝对最短的路径将每个包裹运送到目的地，以节省燃料和时间。

这就是经典的**最优传输（Optimal Transport）**问题：研究如何最有效地将“质量”从 A 点移动到 B 点。

现在，想象另一种工具叫做 GFlowNet。你可以把它想象成一个正在学习如何在迷宫中行走的机器人。它不是一次性规划好整条路线，而是学习一套“规则”（策略），即：“如果我在这个路口，下一步该往哪边转？”它通过在其中穿梭、从错误中学习，最终学会如何从起点高效地到达终点。

重大发现
这篇论文揭示了一个秘密：这个机器人（GFlowNet）实际上是在我们没有明确告知的情况下，就在解决那个递送问题（最优传输）。

以下是论文如何使用简单的类比来解释这种联系的：

1. 同一枚硬币的两面

通常，我们认为这是两项不同的工作：

递送规划师（最优传输）： 计算出完美的地图，确定谁该把什么东西发给谁，以最小化总距离。
行走机器人（GFlowNet）： 学习一套规则，从起点走到终点，并尝试走最短的路径。

作者证明了，如果你正确地设置这个机器人——具体来说，通过明确告诉它在起点要领取多少包裹（“初始流”）——那么机器人追求最短路径的目标，在数学上就等同于递送规划师追求最小化运输成本的目标。

2. “最短路径”的魔力

在普通的迷宫中，机器人可能会绕圈子。但论文显示，当你训练这种特定类型的机器人使其尽可能高效（最小化总“流”或交通量）时，它自然就会停止徘徊。

相反，它会学会只走最短路径。

类比： 想象机器人是一个顺着山坡流下的水滴。如果你想让水最快到达底部，它自然会找到最陡、最短的路径。论文表明，机器人的“学习规则”迫使它的行为表现得就像那个水滴一样，在网络中寻找任意两点之间最高效的路径。

3. “耦合”的秘密

在递送世界中，“耦合（Coupling）”是一份清单，上面写着：“来自仓库 A 的包裹 #1 去往住户 #1，包裹 #2 去往住户 #2。”

论文显示，当机器人完成学习后，它实际上已经秘密创建了这样一份清单。如果你要求机器人从特定的起点开始一段旅程，并观察它最终到达了哪里，它旅程的模式会与最高效的递送计划完美契合。机器人不仅学会了如何行走，它还学会了谁应该去哪里，从而使所有人的总行程距离最小化。

4. 为什么这很重要（根据论文所述）

作者在两种类型的“城市”上进行了测试：

网格城市： 简单的正方形网格。在这里，我们可以将机器人的答案与完美的计算机计算结果进行对比。机器人的答案与完美规划师的结果完全一致。
置换城市（Permutation Cities）： 这些更加复杂，就像洗一副扑克牌一样，每张牌都是一个位置。随着牌组变大，计算机将无法计算出完美的计划。然而，机器人仍然可以学习到一个非常好的近似值，处理那些会让标准计算器崩溃的复杂情况。

核心结论

论文声称，GFFlowNets 实际上是隐藏的最优传输求解器。 通过训练一个机器人在图中高效行走，你实际上是在自动解决移动概率分布且成本最低的复杂数学问题。

作者还提到一个控制机器人行为的“旋钮”（一个被称为 $\lambda$ 的参数）：

将旋钮向一个方向转，机器人会走极短的路径，但可能无法准确送到正确的住户手中。
向另一个方向转，它能完美递送，但可能会采取稍长且弯曲的路线。
找到这两者之间的平衡点，就能获得两者的最佳效果。

简而言之，你不需要两种不同的工具。如果你教会一个机器人在最短路径上行走，它就会在无形中成为世界上最优秀的递送规划师。

技术摘要：你的 GFlowNet 正在秘密学习最优传输方案

问题陈述
生成流网络（GFlowNets）旨在通过有向图中的随机轨迹来采样结构化离散对象。虽然最初是为无环图设计的，但最近的研究已将其扩展到非无环环境。在这些设置中，最小化期望轨迹长度对于提高采样效率至关重要，从而引出了“最小流”（minimum-flow）GFlowNet 的公式化。与此同时，最优传输（Optimal Transport, OT）提供了一个原则性的框架，通过最小化传输成本来比较概率分布，通常通过线性规划（Kantorovich 公式）求解。然而，使用精确求解器在大型图上求解 OT 通常在计算上是难以实现的。

本文通过研究非无环 GFlowNet 的最小流公式是否本质上解决了一个最优传输问题，来填补这两个领域之间的空白。

方法论
作者建立了非无环 GFlowNet 与图上离散最优传输之间的理论等价性。核心方法包括：

理论重构： 作者从非无环 GFlowNet 的最小流优化问题入手，该问题在满足细粒度平衡（detailed balance）和奖励匹配约束的情况下，最小化总流量（等效于最小化期望轨迹长度）。通过将初始边流分布（离开源状态 $s_0$ 的流）固定为与特定源分布 $L(u)$ 相匹配，他们将 GFlowNet 的目标转化为一个线性规划（LP）问题。
等价性证明： 他们证明了这种受约束的 LP 在数学上等价于 Kantorovich 最优传输问题。在此公式中：
- 源分布是定义在集合 $U$ 上的 $L(u)$ 。
- 目标分布是定义在终止状态 $X$ 上的奖励分布 $R(x)$ 。
- 传输成本 $d(u, x)$ 定义为图中 $u$ 与 $x$ 之间的最短路径距离。
- 最优 GFlowNet 策略隐式地学习了最小化总传输成本的最优耦合 $\Pi$ 。
学习算法： 为了在精确 LP 不可行的规模化大图上解决此问题，作者采用了 GFlowNet 的神经参数化。他们利用带有流正则化的轨迹平衡（Trajectory Balance, TB）目标。一个关键的修改是在损失函数中加入了“向左”（leward/left reward）项，以强制执行固定的初始分布 $L(u)$ ，同时结合标准的针对目标分布 $R(x)$ 的奖励匹配。

主要贡献

理论等效性： 本文证明，通过在最小流 GFlowNet 中固定初始流分布，其目标恰好简化为具有图诱导最短路径成本的 Kantorovich OT 问题。因此，最优 GFlowNet 前向策略编码了一个最优传输方案，从其采样轨迹可以恢复出最优耦合。
与 Beckmann 问题的联系： 作者展示了该公式等价于基于图的离散 Beckmann 问题，将 GFlowNets 与经典的网络流理论联系起来。
可扩展的 OT 求解器： 该工作表明，GFlowNet 学习框架可以应用于近似求解基于图的 OT 问题。通过使用神经网络和随机轨迹采样，该方法可以扩展到精确 OT 求解器难以处理的组合空间。
恢复最短路径理论： 作为推论，该构建恢复了先前为非无环 GFlowNet 建立的最短路径理论，表明最优流仅在最短路径的子图上得到支持。

实验结果
作者在两个环境中验证了其理论和方法：

超网格（Hypergrid）环境： 在小型超网格（ $H=10, 15, 20$ ）上，学习到的 GFlowNet 策略所达到的传输成本（ $OT^\star$ ）与通过经典 LP 求解器（POT）获得的精确解相匹配。该方法成功地在不同的源分布（球形和月牙形）下恢复了最优耦合，且没有导致采样偏差。
置换（Permutation）环境： 在对称群 $S_n$ （置换）的 Cayley 图上，该方法在 $n=4$ 和 $n=8$ （此时精确解是可处理的）时恢复了近优解。对于 $n=20$ （此时精确 OT 难以处理），该方法产生了具有较低不动点概率误差的合理近似值。
消融实验： 关于正则化系数 $\lambda$ 的实验证实了轨迹长度（采样效率）与采样最优性（传输方案准确性）之间的权衡。较低的 $\lambda$ 值产生更准确的传输方案，但会导致更长的轨迹。

意义与主张
本文声称揭示了一个“秘密”联系：当被公式化为最小化流时，GFlowNets 本质上正在求解最优传输问题。这项工作的意义在于：

统一性： 它提供了一个全新的理论视角，将 GFlowNet 学习与最优传输统一起来，表明 GFlowNets 可以被视为学习传输映射的一种方法。
实际应用： 它使得将 GFlowNet 学习算法（通过神经网络和采样实现扩展）应用于大规模图 OT 问题成为可能，而这些问题对于精确求解器来说在计算上是极其昂贵的。
框架扩展： 它将 GFlowNet 框架的通用性从采样和生成任务扩展到了计算最优传输领域，提供了一种随机策略，该策略不仅决定了质量如何被传输（where），还决定了如何通过可行的局部移动进行传输（how），并具有近乎最优的路径成本。

作者对未来的影响保持了谦逊，指出虽然该方法在计算上是高效的，但正则化系数 $\lambda$ 需要仔细调优，以平衡最优性和效率。他们建议未来的工作可以探索如何将这些方法应用于学习非归一化分布之间的传输映射。