【OR Talk NO.17 | 组合优化问题的机器学习研究——以图匹配问题为例】https://www.bilibili.com/video/BV1Zf4y1S7Zr?vd_source=7c2b5de7032bf3907543a7675013ce3a

定义：

什么是图匹配？

在三个图片上提取点，包括内点、外点、噪声点；试图在两个或多个图中找到点的对应关系；而在比较时不仅要看点与点之间的相似度，还要看每两个点之间的边的相似度，而有了边就有了图的概念，从而引出graph matching

图匹配vs配准

配准：找到两个点对应关系的同时找到参数化的变换模型，将两个点集配准，关键在于一个transformation模型（相似变换/仿射变换）

图匹配：不假设两组点之间有参数化模型，只是求解对应关系

图匹配形式化的数学模型：

通过SIFT/SURF进行特征点提取，使用相似度计算包含五点的图中的点与包含四点的图中的点的相似度，得到矩阵

 矩阵行的数目为左图点的数目（5），列的数目为右图点的数目（4）

传统方法计算点之间的距离或相似性，用矩阵（存储节点和节点的相似度信息）表示出来，该方法称为线性指派问题，得到矩阵后通过匈牙利算法得到最优解

 而图匹配问题在于还需要计算边与边的相似度，因此由一阶变为二阶

此时，边的信息由矩阵来表征， 行的数目为包含五点图的边数（8），列的数目为包含四点图的边数（4），得到边的相似性矩阵

由得到组合化的线性问题，为两个项相加的组合

而当引入一个Affinity Matrix K时，会使问题变得更简单

对左边的点和右边的点组合进行编码（1a、1b共有5*4=20个），形成对称矩阵

对角计算点3和点b之间的相似性

非对角计算35边和bc边之间的相似性

 写成QAP形式，可以得到一个标量的值来解决问题；一般意义下是NP-hard的

QAP问题：

常规解决方法：

①将离散约束去掉，转化为简单的模的形式，松弛不够紧促，但求解速度快；类似于谱方法求解特征值和特征向量

②将原本{0,1}松弛到实数域[0,1]，得到的松弛较为紧凑，但计算速度慢

③考虑高阶变换，将图转换为超图（行不通，复杂度高），通过图嵌入将高阶信息嵌入到低阶信息

新方法：

拆解矩阵，时间换空间：

 基于分解模型提出路径跟踪算法：

 一开始对其做凸优化松弛，将目标函数变为凸函数，凸优化的好处对解一开始并不敏感且速度快；慢慢将问题变为凹函数的形式，最后可以自然收敛为离散解

多图协同匹配：

父母来源于不同种族，因此匹配难度较高，而双方拥有一个共同的儿子，通过父亲和儿子匹配，母亲和儿子匹配，传递匹配关系

思路：G1与G2匹配难，通过中间图G3来匹配

问题：一味去算两个图的匹配相似度并不可取，相似度来源于特征，而特征提取时可能会受到噪声的影响；高斯模型很难刻画复杂的相似度关系

参照机器学习，考虑正则，提出consistency思想

consistency：

假设有三个图，若为真值，则是consistent；通过定义的值来表征consistency，值越大则代表解的质量越好

 用衡量权重，会越来越大

机器学习改善：

优化权值，可学习的权值

深度学习优化：

SM为谱方法，但是为近似解；损失函数有缺陷，类似光流

SM：

给两张图，可以用两张图的点得到超点，构建一个新的图；找到最大特征向量

损失函数：

采用第一误差 

改进：

论文1：

Learning Combinatorial Embedding Networks for Deep Graph Matching

创新点：

①在引入CNN后，引入GNN

②将SM改为Sinkhorn

③损失函数设计为Permutation Loss（交叉熵函数）

使用CNN提取点特征之后，再使用GNN提取graph的特征做embedding，升维度

使用intra-GNN更新图节点信息，交替的对每个点做如此操作

将局部边的问题压缩到点上，变成线性指派问题，大大提高了计算量

Sinkhorn Algorithm：

Sinkhorn：对一个非负的矩阵交替的对它的行和列归一化

Sinkhorn是一种算法，但可以通过网络的形式实现

行和列交替的存储在一起，收敛得到双随机矩阵（每一列和每一行加和为1，类似于概率分布）

双随机矩阵可以归一化得到解，使用交叉熵函数得到损失函数

Cross-GNN：

匹配问题一般可能会给到两个图，所以可以使用Cross-GNN协同embedding，使左右图的信息关系可以得到传递

左右相互传递，使得信息接近，更利于后期做匹配；匹配结束再进行embedding可以加强效率 

论文2：

Neural Graph Matching Network：Learning Lawler's Quadratic Assignment Problem with Extension to Hypergraph and Multiple-graph Matching

 Lawler's QAP：没有太多的CNN层面的东西需要学习，假设CNN已经学好了

直接在association graph上做embedding，而不是在两个图各自上做embedding或匹配

考虑多个图的场景，将两两匹配的解堆叠到一起，寻找最大特征向量

考虑高阶情况（超图匹配）

 Association Graph：

在关联图上做embedding，得到Sinkhorn，得到最优解

Edge-embedding：

在点和边的维度上都使用edge-embedding，进一步提升模型的容量，并提升精度

Sinkhorn Embedding：

考虑约束问题，使得embedding的得分框在行和列上没有冲突

经过Sinkhorn后，提升明显

在网络结构设计上，对组合问题不能直接学习CNN的特征

Hyper-Graph Matching：