使用POT库计算相同输入的Gromov距离非零问题求助

问题梳理 #

用Python Optimal Transport（POT）库计算FGW或Gromov距离时碰到了一个坑：计算同一分布自身的距离，结果居然不是0。测试了深度3二叉树的最短路径距离矩阵+均匀直方图的案例，确认距离矩阵是对称且满足三角不等式的，但库返回的耦合根本不是最优解——明明单位矩阵对应的距离是0，库算出来却非零。

看算法日志发现收敛很快，明显是陷入局部极小了。手动用单位矩阵初始化能得到正确结果，但gromov_wasserstein函数不支持自定义初始传输计划，所以得自己生成满足直方图p和q约束的随机耦合。

生成满足边际约束的随机传输计划 #

下面是三种实用的方法，按需选用：

方法1：Sinkhorn迭代投影随机矩阵 #

先生成随机非负矩阵，再用Sinkhorn迭代把它投影到满足p和q边际约束的耦合集合里：

import numpy as np
from ot.utils import sinkhorn

def random_coupling(p, q, reg=1e-3, max_iter=1000):
    n, m = len(p), len(q)
    # 生成随机非负矩阵
    rand_mat = np.random.rand(n, m)
    # 用Sinkhorn迭代投影到符合边际的耦合
    coupling = sinkhorn(p, q, np.log(rand_mat), reg, max_iter=max_iter)
    return coupling

• 注意：reg是正则化参数，越小越接近严格的边际约束，但迭代次数会增加；如果要无正则的严格耦合，可以试试后面的方法。

方法2：随机置换矩阵凸组合（适合均匀分布） #

如果p和q都是均匀分布（比如p = np.ones(n)/n），可以直接用多个随机置换矩阵的凸组合生成耦合：

import numpy as np

def random_uniform_coupling(n, perm_count=10):
    coupling = np.zeros((n, n))
    # 生成和为1的随机权重
    weights = np.random.dirichlet(np.ones(perm_count))
    for w in weights:
        # 生成随机置换矩阵
        perm = np.random.permutation(n)
        perm_mat = np.zeros((n, n))
        perm_mat[np.arange(n), perm] = 1
        coupling += w * perm_mat
    return coupling

• 注：perm_count越大，耦合的随机性越强；非均匀分布的话，可以先把p/q拆成均匀分块再扩展这个方法。

方法3：采样联合分布生成近似耦合 #

用多分类采样直接生成满足边际的耦合，简单粗暴：

import numpy as np

def random_coupling_via_sampling(p, q, sample_num=10000):
    n, m = len(p), len(q)
    # 按p采样行索引，按q采样列索引
    rows = np.random.choice(n, size=sample_num, p=p)
    cols = np.random.choice(m, size=sample_num, p=q)
    # 统计频次并归一化
    coupling, _, _ = np.histogram2d(rows, cols, bins=(n, m))
    coupling = coupling / sample_num
    # 微调确保严格满足边际（可选）
    row_sum = coupling.sum(axis=1, keepdims=True)
    col_sum = coupling.sum(axis=0, keepdims=True)
    coupling = coupling * (p / row_sum) * (q / col_sum).T
    return coupling

• 注：sample_num越大，耦合越接近真实边际约束，适合快速生成近似解。

额外建议 #

• 生成随机耦合后，要是gromov_wasserstein不支持传入初始值，可以直接调用POT底层的迭代函数，比如ot.gromov._gromov_wasserstein_iteration，把初始耦合传进去
• 可以多跑几次不同的随机初始值，取最小的距离结果，避开局部极小
• 均匀分布的场景优先用方法2，生成的耦合更贴合问题对称性

内容的提问来源于stack exchange，提问作者Thibault HERVIER