关键词:
模式识别
图匹配
神经网络
整数线性规划
深度图匹配
摘要:
图匹配旨在建立两个图之间的结点映射关系,是一个经典的NP难组合问题。近几年,大量的研究者开始借助深度学习技术来构建端到端的可训练架构,以此对图匹配问题进行求解。这一端到端的管道架构被称为深度图匹配模型,其包含两个重要模块,图表示学习模块和图匹配问题求解器。然而,在目前深度图匹配模型研究中,存在着两个待解决的重要问题。第一,主流的深度图匹配模型通常对图匹配问题进行连续松弛,以使得模型可以基于梯度下降法来优化可训练参数。但是目前没有研究说明,基于学习的求解技术是否应该对图匹配问题进行连续松弛,以及图匹配问题的求解质量与模型的匹配精度存在什么联系;第二,图表示学习模块对手工构造的简单图的学习能力有限,导致结点的嵌入表示可区分性差,使得结点亲和力度量不准确,最终导致模型的匹配精度受损。本文的研究内容围绕着深度图匹配模型的两个重要模块开展,并针对上述两个关键问题,结合整数线性规划和图表示学习技术,研究基于可微整数规划的深度图匹配模型。同时,本文以关键点匹配任务为应用背景,定量地评估本文研究工作的有效性。具体研究内容和主要贡献如下:(1)本文首先对深度图匹配模型中的松弛图匹配方法展开分析和研究,提出了两个重要猜想。第一,深度图匹配模型的输出与图匹配问题的最优解是等价的,都是描述目标之间的真实映射关系。第二,图匹配的连续松弛会损失图匹配问题的求解精度,而这种损失是难以通过图嵌入技术弥补的。通过三个实验对上述两个猜想进行了验证,其结果表明图匹配问题的求解质量与模型的匹配精度呈正相关。并且,由于应用了图嵌入技术学习结点的高阶嵌入表示,降低了结点相似性度量的难度,因此适当的放松图匹配的约束条件是可行的。(2)在研究(1)的基础上,本文给出了精确求解图匹配问题的MILP公式,并设计了一个可微整数线性规划求解器(DIP)进行求解。该求解器通过质量感知求解算法对MILP公式进行计算,然后借助隐式插值技术来构造有意义的梯度信息,以实现将其作为黑盒嵌入到可训练的网络架构中。为了检验DIP的有效性,同时验证(1)中提出的两个假设,我们为现有模型装配上该求解器,并称这一改装后的模型为DIP-GM。实验结果表明DIP具备可扩展性,可以在网络训练中作为黑盒使用,并且提高了深度图匹配模型的匹配精度。(3)经过(1)(2)的研究后得知,深度图匹配模型的匹配精度极大程度地依赖图表示学习模块的特征学习能力。因此,本文从提升图表示学习模块的学习能力出发,设计了一个基于自注意力机制的图嵌入网络GSAN。该网络由空间编码器和多头注意力机制组成。首先,网络使用空间编码器将结构信息嵌入到结点的表示向量中,然后,利用多头注意力机制学习所有结点之间的关联性,以细化结点特征。同时,为了增添更多的全局信息,我们还引入结点介数作为补充特征。(4)整合上述三项研究工作,本文最终设计了一个基于可微整数线性规划求解器的端到端可训练架构,称之为GSAN-GM。GSAN-GM首先使用GSAN进行图嵌入,获得结点的高阶嵌入表示。接着根据得到的结点表示向量构建边的表示向量,并进行结点亲和力度量和边亲和力度量。最后,利用求解器求解图匹配问题,并将得到的解作为模型的结果返回。本文在两个公共图像数据集上训练和验证GSAN-GM的有效性,其结果表明不仅具有跨类别的泛化能力,还能够处理大小不同的输入图。同时,GSAN-GM的平均匹配精度超过了大多数的深度图匹配模型,并且在自行车、公共汽车、桌子等多类任务上的匹配精度优于最先进的匹配精度。