如何在考虑点置换的情况下比较两个距离矩阵

问题本质 #

两个未对齐点序的距离矩阵，本质是两个无向带权完全图的邻接矩阵。常规的距离矩阵比较方法（包括Mantel检验、逐元素差异计算、相关系数计算）都默认两个矩阵的行/列索引存在一一对应的固定映射，一旦点序被置换，这类方法就会得出完全错误的结论，比如给出的两组3点距离矩阵：
第一组点n1、n2、n3的距离矩阵：

0 4 5
4 0 3
5 3 0

第二组点m1、m2、m3的距离矩阵：

0 3 4
3 0 5
4 5 0

直接逐元素比对会得到矩阵差异很大的结果，但实际上只要将第二组点按m3→n1、m1→n2、m2→n3的映射重排，两个矩阵完全一致。
暴力枚举所有点置换取最高相似度的方法时间复杂度为O(n!)，仅能支撑n<10的极小场景，完全无法适配稍大规模的点集。一维场景下的最优置换是线性分配问题，可以通过排序或匈牙利算法快速求解，但距离矩阵的匹配存在点对之间的二阶约束，无法直接套用一维方法，需要根据场景选择以下方案：

具体可行方法 #

• 小规模场景精确解：带权图同构算法
  如果需要得到精确的最优点映射，且点规模n在100以内，不需要暴力枚举排列，可以使用带权图同构的求解算法：
  首先用Weisfeiler-Lehman（WL）测试快速筛选可匹配点：初始给每个点分配标签为「该点到其余所有点的非零距离值排序后的元组」，之后每一轮迭代将每个点邻居的标签聚合排序后，和自身标签合并生成新标签，不断迭代直到标签不再变化。最终标签完全相同的点就是存在映射关系的对应点。
  对给出的3点例子，仅需一轮WL测试就能得到正确映射：
  • n1的非零距离排序为[4,5]，和m3的非零距离排序[4,5]一致，二者匹配
  • n2的非零距离排序为[3,4]，和m1的非零距离排序[3,4]一致，二者匹配
  • n3的非零距离排序为[3,5]，和m2的非零距离排序[3,5]一致，二者匹配
    1-WL测试的时间复杂度为O(n² log n)，对绝大多数非刻意构造的距离矩阵，都能直接得到精确的置换结果。如果存在距离值重复、1-WL无法区分的点，可以配合回溯剪枝的精确图匹配算法搜索剩余可能的映射，实际运行效率远高于暴力枚举，n在几十量级时都能快速返回结果。
• 中大规模场景近似解：二次分配问题（QAP）求解
  点序对齐的目标可以被形式化为：找置换矩阵P，使得重排后的矩阵差异最小，即最小化目标函数||P·D1·P^T - D2||_F（其中||·||_F为矩阵的弗罗贝尼乌斯范数，即逐元素差的平方和开根），这是二次分配问题的标准形式，属于经典的NP难组合优化问题，不存在通用的多项式时间精确解法，但有非常成熟的近似求解方案：
  • 谱方法：对两个距离矩阵分别做特征分解，将特征值按从大到小排序后，对齐特征向量的符号歧义，即可快速得到近似的点置换映射，时间复杂度和矩阵特征分解一致为O(n³)，可以支撑n上千的大规模场景。
  • 启发式优化：如果对匹配精度要求更高，可以用模拟退火、梯度下降、蚁群算法等启发式方法迭代优化置换矩阵，在可接受的时间内得到更接近全局最优的匹配结果。
• 统计检验场景适配：置换检验修正
  如果做距离矩阵比较的目的是做类似Mantel检验的相关性显著性判断，不需要得到精确的点对应关系，可以对检验逻辑做修正：将「所有可能置换下两个矩阵的最大相关系数」作为检验统计量，通过随机置换其中一个矩阵的行/列生成零分布，再用实际计算得到的最大相关系数在零分布中的分位数判断显著性，避免固定点序带来的结果偏差。

注意事项 #

一维数组的最优置换是线性分配问题，仅需要考虑单个点的特征匹配，复杂度极低；但距离矩阵的匹配需要同时满足所有点对之间的距离约束，属于二阶匹配问题，不存在普适的低复杂度精确解法，需要根据自己的点规模、精度需求选择对应的方案。

内容的提问来源于stack exchange，提问作者M.Z.