摘要
图匹配涉及基于边到边亲和矩阵的组合优化问题，通常可以表述为劳勒的二次指派问题（Quadratic Assignment Problem, QAP）。本文提出了一种直接利用亲和矩阵（等效于关联图）进行学习的QAP网络，将匹配问题转化为一个受约束的顶点分类任务。关联图通过嵌入网络进行顶点分类的学习，随后采用Sinkhorn归一化和交叉熵损失函数实现端到端的学习。我们进一步通过引入基于Sinkhorn的匹配感知约束以及虚拟节点来处理图大小不等的问题，改进了关联图上的嵌入模型。据我们所知，这是首个直接针对一般劳勒QAP进行学习的网络之一。相比之下，近期的深度匹配方法主要集中在分别学习两个图中的节点/边特征。我们还展示了如何将该网络扩展到超图匹配及多图匹配。在合成图和真实图像上的实验结果表明了其有效性。对于纯QAP任务，在合成数据和QAPLIB基准测试中，我们的方法不仅具有竞争力，甚至在显著减少时间成本的情况下超越了现有的最先进图匹配和QAP求解器。项目主页提供于 http://thinklab.sjtu.edu.cn/project/NGM/index.html。