基础科学中的人工智能︱如何用机器学习方法求解排列型组合优化问题？

排列（permutation）作为一个重要的离散数学概念，许多实际问题可以被刻画为n个候选对象的排列。基于给定的目标函数求解最优排列具有丰富的理论和应用价值。特别地，在以排列型问题为代表的组合优化问题中，近年来机器学习、尤其是深度学习方法在国内外研究中不断涌现，机器学习已经被证明能够提升传统非学习求解方法的性能，相关技术已应用于计算机视觉、数据挖掘、运筹优化等领域。

本推文介绍了上海交通大学汪润中博士的研究成果，其博士毕业论文《排列型组合优化问题的机器学习求解方法研究》得到了2024年度博士学位论文激励计划的提名。论文围绕排列型组合优化问题传统求解器的痛点，提出了使用机器学习模型替代与融合传统方法的思路，为包括图匹配问题、二次指派问题、基数约束优化问题等排列型组合优化问题做出了更有效的机器学习求解方法，同时将这些求解器进行了开源，为该领域做出了贡献。

博士学位论文下载地址：https://www.ccf.org.cn/Focus/2024-11-21/834371.shtml

本文作者为王一鸣，审校为龚裕涛。

01 研究背景

什么是组合优化问题(combinatorial
optimization problems，CO)？以排列型问题为代表，即是基于给定的目标函数求解最优排列。本文关注的是排列型组合优化问题(permutation-based combinatorial optimization problems)，例如排序、匹配和回路问题。图1展示了一些关于排列型组合优化问题的示例。对于排列型组合优化问题，一个关键的步骤是如何求解。排列型组合优化问题的求解面临的主要挑战包括如下几方面。

图1 排列型组合优化问题的代表性例子

（1）针对纯机器学习求解方法，由于排列型组合问题天然具有离散性，而神经网络的输入输出和中间层均具有连续性，那么该如何设计神经网络求解器?

（2）针对融合传统算法的学习求解方法，机器学习方法在分类、回归等模式识别问题中表现更佳，传统算法则擅长针对问题精确求解，那么该如何设计可融合的范式?

（3）针对所有机器学习方法，由于NP难问题无法通过传统算法大量获得最优解标签，故不能使用简单且稳定的监督学习方法，因此该如何为NP难的排列型组合优化设计训练方法?

汪润中博士的研究针对上述几种挑战，做出了以下主要贡献：

面向主要技术难点——如何为排列型组合优化问题的纯机器学习求解方法设计神经求解器，该研究（1）提出了首个面向图匹配求解的神经网络。（2）提出了首个面向二次指派问题的神经网络。（3）提出了首个面向基数约束优化问题的神经网络。

面向融合方法的主要技术难点——如何设计融合范式，该研究实现了：（1）在经典的A*树搜索中融合深度学习以实现提速。（2）在深度图匹配中融合传统图匹配求解器以实现无监督预训练。（3）将启发式求解器嵌入双层优化的强化学习框架以提升求解精度。

注意到目前的排列型组合优化问题缺乏高质量、应用范围广的开源求解框架，作者将积累的技术整合、扩展后，该研究（1）开发了面向下游应用的图匹配通用算法库pygmtools。（2）开发了面向科研的深度学习排列型组合优化系统ThinkMatch。（3）开发了面向国内自主研发的深度学习框架“计图”的图匹配框架。

本推文将节选该博士论文的精彩内容分享给读者，按照从特殊到一般，从求解到训练的流程，重点描述图匹配问题的求解、二次指派问题的求解、如何使用无监督方法训练求解器。

02 图匹配问题的求解

首先简单介绍一下图匹配问题。图匹配（graph matching）旨在构造两个图结构之间的节点匹配关系。通过引入机器学习，可以在考虑噪声的同时高效地建模图匹配中的相似度函数，使得图匹配问题在数学上的最优解具有正确的物理意义。

图匹配问题的分类有哪些？给定两个图结构，它们之间的匹配问题为二图匹配。对于经典的二图匹配问题，也可以被称为二次指派问题。基于二图匹配，最近的研究也尝试研究了超图匹配，即图片包含比二阶更高阶的相似度信息，和多图匹配，即同时匹配多个图结构。

对于上述问题，都需要面对一个基础性问题：如何合理地设计点特征、边特征提取器以及相似度模型，将真实世界的匹配任务转化为等价的数学形式。但是，人工设计的相似度函数可能缺乏足够的模型表达力，会导致数学形式的最优解不符合正确的匹配结果。基于上述观察，本研究的动机来自如下两个方面：

（1）将图匹配问题转换为线性指派问题。通过图嵌入网络，特别是图卷积网络，将图结构嵌入到节点特征向量中，可以将图匹配问题转换为线性指派问题。

（2）设计面向组合优化的排列损失函数。面向排列型组合优化，本研究开发了一种针对Sinkhorn网络的排列损失函数，该类损失函数还可以处理大小不同的图。

基于以上动机，如图2所示，作者提出了三种不同的深度学习图匹配方法PIA-GM、PCA-GM、IPCA-GM。它们分别使用了图像特征提取、图内节点嵌入、跨图节点嵌入、迭代跨图节点嵌入、相似度函数、Sinkhorn 网络几个主要的模块。三种算法的核心思路一致，即通过图嵌入方法将问题简化，进而进行可微的精确求解。接下来将具体介绍各个模块的思路与结构。

图2 本节提出的深度学习图匹配方法概览

图像特征提取。若问题输入为图像，可以使用了一个CNN网络来提取关键点的特征向量。为了与前序工作的公平地对比，采用在ImageNet分类任务上预训练的VGG16网络作为主干网络。

图内节点嵌入。利用一个多层的节点嵌入模型构建了二阶和高阶的图相似度信息。节点嵌入模型采用类似图卷积网络的消息传递机制，节点的特征由其邻接节点以及该节点自身作为信息源，进行高效的特征更新。

跨图节点嵌入。在图内节点嵌入的基础上，跨图的节点嵌入能够进一步提升匹配模型的性能。首先使用了浅层嵌入网络中预测得到的相似度信息，通过构建相似度函数以及Sinkhorn迭代，预测一个双随机的相似度矩阵。

迭代跨图节点嵌入。利用了包括跨图嵌入层和图内嵌入层。基于嵌入的特征可以计算一个相似度矩阵，进而通过Sinkhorn算法得到一个双随机矩阵S。

相似度函数。通过前述的节点嵌入模型，两个图之间结构的相似度信息被编码在了节点嵌入空间内。因此，模型允许将传统的二阶相似度矩阵K简化成线性的形式。

Sinkhorn 网络与线性指派问题求解。Sinkhorn算法接受任何非负的方阵作为输入，输出一个双随机的矩阵。通过不断迭代公式直至收敛，最终得到一个双随机矩阵。在训练过程中，双随机矩阵S是模型的预测输出。

03 二次指派问题的求解

Lawler 形式的二次指派问题作为一类常见的排列型组合优化问题，覆盖了前文所提到的图匹配问题，同时囊括了布局规划、电路设计等重要的应用场景。由于前文所述的神经网络求解方法专为图匹配问题设计，该研究从图匹配出发，面向更一般的二次指派问题，提出了更一般的神经网络结构进行求解。

如表1所示，作者总结了现有的工作。可以看出，当前最先进的图匹配和二次指派问题求解器中，多数只能求解特殊情况的二次指派问题，同时几乎没有多图匹配求解器。针对现有方法的不足，作者提出了NGM、NHGM、NMGM算法，可以做到：

（1）设计一个神经网络模型直接处理最一般的 Lawler 形式二次指派问题；

（2）神经网络同时支持监督学习和非监督学习；

（3）将神经网络求解器扩展到高阶(三阶)指派；

（4）将神经网络求解器扩展到多图匹配。

表1 机器学习图匹配和二次指派方法的技术总结

NGM等算法的概览如图3所示，其中主要包括特征提取、伴随（超）图构建、（超）图嵌入、Sinkhorn匹配结果等过程。它们的核心思路一致，即通过将（超）图匹配任务通过相似度矩阵转化为伴随（超）图的顶点分类任务，从而求解图匹配问题。

图3神经网络二次指派求解器概览

由于三种算法的流程比较类似，所以这里只具体介绍NGM算法的框架。如图4所示，NGM算法的框架主要包括：从真实图像中构造相似度矩阵、具有排列意识的伴随图嵌入、基于 Sinkhorn 层的节点分类、端到端训练的损失函数四个模块。接下来具体介绍各个模块的思路和结构。

图4 用于求解二图匹配问题的NGM神经网络架构

从真实图像中构造相似度矩阵。图像特征通过可学习的CNN层(例如VGG16)提取。然后在每个节点特征上采用两次样条卷积层产生精细化的特征。由特征空间中两个节点之差得到边特征。此外，图像特征提取网络还包含一个分支，通过对relu5_3层的输出进行最大池化产生池化全局特征。两个图的池化全局特征随后被拼接起来，传递到一个全连接层，通过tanh激活函数，产生全局特征。基于加权内积，通过使用全局特征作为权重，构建节点相似度矩阵和边相似度矩阵。二次指派问题的相似度矩阵是根据节点相似度矩阵和边相似度矩阵分解式构建的。

具有排列意识的伴随图嵌入。图匹配问题等价于在伴随图中选择对应的顶点。本研究采用了GCN作为基础架构对伴随图上的顶点进行分类。作者开发了一个具有排列意识的嵌入模型：在每一层中，通过分类层和Sinkhorn层得到一个双随机矩阵，接着进行向量化。预测的双随机矩阵被拼接到顶点嵌入中，从而在嵌入层中考虑排列约束。

基于Sinkhorn 层的节点分类。由于图匹配等价于关联图上的顶点分类，因此采用带有Sinkhorn网络的顶点分类器来预测匹配结果。

端到端训练的损失函数。对于存在监督信号的情况，可以采用排列损失函数进行监督训练。

04 无监督方法的求解器训练

现有图匹配研究中广泛考虑的二图匹配、多图匹配场景已在前文进行了介绍。在此基础上，本节进一步考虑了更加一般化的图匹配任务类型，如图5所示，其中包括多图匹配的扩展——混合模态多图匹配以及由于噪声、自遮挡等因素的存在，实际匹配任务中常见的挑战——外点(outlier)和部分匹配(partial matching)。

图5 混合两种模态的匹配问题和含外点、部分匹配的图匹配任务实例

在完成了对图匹配任务与二次指派任务求解器的设计后，作者提出，当前监督式的深度图匹配需要对大规模训练数据进行昂贵的标注，这限制了深度图匹配方法的实际应用。在此基础上，观察到最近无监督图像分类模型的成功，作者发现它们具有一个相通的设计理念，即通过最小化两个分支在同一数据上预测值的差异实现无监督学习。受此启发，该研究提出了一个简单而有效的无监督学习框架，它融合了传统图匹配求解器和深度学习模型：在差异最小化的框架下，以孪生网络的形式，不可微的传统求解器和可微分Sinkhorn分支共享一个CNN主干网络。

图6为作者提出的基于差异最小化的图匹配无监督学习框架，其中主要包括：特征提取、Sinkhorn 计算节点匹配、梯度截断、编码结构信息、差异最小化方法几个主要模块。其核心思路为最小化传统求解器与Sinkhorn分支的差异，从而达成无监督训练的效果。接下来将具体介绍各个模块的思路与结构。

图6 无监督的图匹配学习框架概览

特征提取。本研究中的无监督图匹配学习框架是一个面向计算机视觉的模型，接受图像作为输入。图像经过VGG16网络处理。

利用Sinkhorn计算节点匹配。依次进行行归一化和列归一化迭代，得到双随机矩阵。这一方法得到的解可被视为对匈牙利算法的可微分近似。

编码结构信息。图匹配求解器接受图像中的CNN特征和结构信息，并且将结构信息编码为图的边。

融合图匹配求解器的差异最小化方法。本研究中无监督学习的目标函数即为最小化图匹配求解器的匹配结果和利用Sinkhorn直接匹配的匹配结果的差异，即经过学习后，Sinkhorn分支的匹配精度应该与图匹配求解器一样准确。

基于渐近指派的图匹配求解器。基于无监督学习框架，作者讨论了在统一的渐进指派框架下，如何利用传统算法求解二图匹配、多图匹配和混合模态的多图匹配问题。渐近指派算法通过渐近式的Sinkhorn和匈牙利指派，将目标函数逐步投影到可行空间中。当参数τ减小时，Sinkhorn 算法的输出会越来越接近匈牙利算法。因此，通过逐步减小τ，Sinkhorn可以让输入矩阵逐步接近排列矩阵，再通过匈牙利方法得到匹配结果。

关于如何用机器学习方法求解排列型组合优化问题的更多内容，请读者查阅博士学位论文《排列型组合优化问题的机器学习求解方法研究》，下载地址为：https://www.ccf.org.cn/Focus/2024-11-21/834371.shtml。

作者介绍

汪润中，浙江杭州人，本科毕业于上海交通大学电子系，博士就读于上海交通大学计算机系，研究方向为机器学习求解 （排列型）组合优化，导师为杨小康教授和严骏驰教授。更多信息请查询汪润中博士的个人主页：http://runzhong.wang。

导师介绍

杨小康，上海交通大学教授，国家杰青基金获得者，上海高校特聘教授（东方学者），主要研究视频编码与通信、图像处理与模式识别、视频分析与检索。

严骏驰，上海交通大学教授，国家级青年人才、科技部新一代人工智能重大项目、基金委人工智能重大研究计划项目负责人，教育部深度学习资源建设首席专家。主要研究兴趣为机器学习及交叉应用。更多信息请查询严骏驰教授的实验室主页：https://thinklab.sjtu.edu.cn。