在今年的CVPR上，AR公司亮风台提出完全可训练的图匹配方法，论文《Learning Combinatorial Solver for Graph Matching》入选CVPR 2020 Oral presentation（约5%比例）。据了解，在CVPR 2019上，亮风台投影AR新算法同样入选 Oral环节，该成果为投影AR技术应用落地提供了重要的技术基础。
在计算机视觉领域，基于学习的图匹配方法已经有十多年的发展和探索史，近几年发展和普及速度更迅速。然而，以往的基于学习的算法，无论有无深度学习策略，都主要集中在节点学习和/或边缘仿射的生成上，而对组合求解器的学习关注较少。
亮风台及其合作伙伴提出了一个完全可训练的图匹配框架，在该框架中，仿射学习和组合优化求解并不像以往的许多技术那样被明确地分开。团队首先将两个输入图之间建立节点对应的问题转化为从一个已构造的分配图中选择可靠节点的问题。随后，采用图网络块模块对图进行计算，形成各节点的结构化表示。最后为每个节点预测一个用于节点分类的标签，并在排列差分和一对一匹配约束的正则化下进行训练。
为了进行评估，新算法在四个公共基准上进行了测试，与包括非学习和基于学习的算法在内的八个最新基准进行了比较。该算法对噪声和异常值具有较强的鲁棒性，总体上优于所有的基线算法。
总体来说，新成果提出的图匹配学习框架有三个方面的贡献：
• 通过构造一个给定两个待匹配输入图的赋值图，将图匹配学习转化为节点选择学习；
• 将仿射学习和组合优化求解结合到一个统一的学习框架中，并扩展了用于结构表示和关系推理的图形网络块模块；
• 设计了一个新的损失函数，其中施加一对一匹配约束来监督网络的训练。
这些实验的源代码链接在论文中可以找到，原文链接：
http://openaccess.thecvf.com/content_CVPR_2020/html/Wang_Learning_Combinatorial_Solver_for_Graph_Matching_CVPR_2020_paper.html
新算法介绍：
1. 基于学习的图匹配
传统图匹配的研究主要依赖于手工构建的仿射关系，这些仿射关系作为组合求解器的输入。这种预先定义的参数关联模型会限制捕捉真实匹配任务结构的灵活性，不合适的关联模型可能会使匹配求解器偏离真实匹配解。
针对这一问题，图匹配的学习在提高匹配精度方面显示了其优越的性能，这主要是通过学习图亲和力度量的参数来代替手工构建的亲和力度量来提高的。大多数传统的学习图匹配算法都是有监督的算法，需要对每个正图中的每个节点对应关系进行详细的标记以进行训练。这些算法分别使用大余量方法、非线性逆优化和基于平滑的技术以有监督的方式训练匹配参数。与有监督方法相比，无监督方法不需要大量的节点级标记。后来，Leordeanu等人为二阶以上约束模型提供一个半监督学习公式。与这些方法不同，Cho提出为类的所有实例参数化一个图模型，并学习其结构属性以进行可视化对象匹配。
尽管深度学习技术在许多领域都显示出强大的威力，但关于图形匹配的深度学习的文献仍然有限。为数不多的开创性研究主要是对深网络中的参数亲合函数进行编码，以便在计算出的节点和边缘亲合下获得正确的匹配分配。Zanfir和Sminchisescu将图匹配作为一个二次指派问题，在使用深参数特征层次表示的一元和成对节点仿射下进行。它采用谱匹配作为组合求解器，对反向传播具有可微性。Wang等人使用图卷积网络（GCN）框架作为节点嵌入模块，该模块聚合图结构信息以生成节点音调相似性。通过这种方法，图匹配被放松为线性分配，并采用Sinkhorn网作为组合求解器。
我们的工作属于深度学习算法组。与以往的方法相比，我们的方法不仅关注于亲和函数的学习，而且关注于组合求解器的学习，它们被有效地组合成一个完全可训练的图网络。为了提高匹配精度，我们在学习框架中引入了强结构表示和它们之间的关系归纳偏差，并通过实验验证了其良好的性能。
2. 问题描述
2.1图匹配问题
2.2 匹配作为节点标注问题
图1. 分配图构造示例在过去的几十年中，针对上述图节点选择问题已经提出了许多算法。最近的一些研究包括使用特征向量技术在分配图中找到主要的强连通簇，以及采用Markov随机游走的统计数据来选择可靠的节点。
与这些手工设计的算法不同，本文提出了一种数据驱动的方法，该方法能够学习如何解决整数二次程序（IQP）问题。
3．我们的方法：群组敏感的图网络框架
4．实验
4.1 模拟2D点集
4.2 CMU House数据集
4.3 Willow数据集
表1显示了我们的算法与基准算法的匹配精度（[5、15、17]的结果引自[15]）。
5. 结论
为了提高匹配精度，提出了一种新的图形匹配深度学习算法。我们首先将输入图之间建立节点对应的问题转化为从构造的指派图中选择可靠节点的问题。为了解决节点分类问题，我们提出了一种完全可训练的网络，该网络嵌入图网络块模块，通过对每个节点的邻域进行卷积，形成其结构化表示。此外，还提出了一种新的损失函数来编码一对一的匹配约束，以指导网络的训练。实验结果表明，我们的图匹配算法对噪声和离群点具有较强的鲁棒性，并优于目前最先进的算法。
