GOT

《GOT: An Optimal Transport framework for Graph comparison》

在开始之前补充一些laplacian相关的知识。L=D-W，进行特征分解，L=UAU_T，A为对角矩阵，对角上是特征值，从小到大，一定有0；U是特征向量组成的矩阵。一般会想得到图的signal，每个节点一个，有重要公式，强连接的节点的signal会比较接近，当保证低频时signal就会比较smooth，因为signal会尽量比较接近。L的特征向量对signal有一定的表示意义。特征值较小代表低频，较大代表高频。
除此之外还有补充一点基本矩阵知识，L=UAU_T，这里的U与U_T是正交的，也就是相乘等于单位矩阵，逆等于对方。

正文开始。

为了了解最优传输读了COPT，发现它是在GOT模型基础上的，所以先来读读这个。两篇都是nips上的，之后根据需求看要不要dig一下COPT。

由题目不难知道，文章的重点就是最优传输OT和graph comparison。作者提出的框架总体上而言可以干两件事：计算两个graph之间的距离（在进行未知置换之后），以及相同结点数量的graph之间的数据传输。可以说很模糊了。具体而言，作者想得到graph signal的一个分布，然后得到两个分布之间的差距。作者还定义了一种新的对齐任务：找一个置换矩阵，使要被对齐的两个graph之间距离最小。
大概知道在干什么了那就走模型！

一点preliminary。亲切的graph相关，无向带权重的图G，N个节点，E条边，邻接矩阵W，度矩阵D——还是对角的，节点i的度是i所连接边的权重之和。最后就是拉普拉斯矩阵L=D-W，以及graph signal是N维向量。

Smooth graph signals

这里用了很多别人文章的东西，闲了再看证明。首先是何谓smooth graph signal，根据这张图简单解释一下：

这三张图中G1的signal是最smooth的。作者认为，高权重相连的点的signal应该是接近的。所以G2和G3中红色和蓝色signal方向完全相反，相连是不合适的。
也是借鉴别人干的，作者让两张图的signal符合高斯分布，让拉普拉斯矩阵的伪逆矩阵作为协方差矩阵：

有了distribution就要算distance了，我们比较熟悉的wasserstein距离长这样。这里可能和常见的不大一样，范数里面不是x-y，结合整个式子和上下文来看，作者想要表达的就是符合G1中signal分布的x经过T变换可以得到G2中signal的分布。

两个高斯分布的wasserstein距离是别人算过的，公式为：

带进高斯分布的参数可以得到：

之前说的T变换（optimal transportation mapping）为。这里不知道应该怎么推，没在reference里看到。
下面的图解释了一下上面说的wasserstein距离的有效性，G2和G3都是G1去掉两条边得到的，他们拉普拉斯矩阵差的范数是一样的，但w2是不一样的，可以看到G3的小很多，而它去掉边的变化并不明显。

Graph Alignment

这一部分讲作者的新概念对齐任务。需要找一个permutation矩阵，重新排列点，然后计算W2。作者使G2中的点进行变换。

我们想要的是：

代入上面已知的式子：

GOT

求解这个W2的难点在于置换矩阵P的约束，因为这是一个离散优化问题，有阶乘级的可行解（并不知道为什么）。所以作者重新规定了一下这个约束。引入Sinkhorn operator，给定一个n阶方针P，和一个较小的常数τ>0，通过下面这个式子对P的行和列进行归一化：

A和B都是对角阵，通过迭代进行更新：

有。所以要解决的问题变为：

下图是个置换矩阵做对齐的例子。

这个式子是非凸的，不能直接用梯度下降。所以来求期望，设P服从某个参数为θ的分布：

作者让这个q_θ为多元高斯分布。代入均值和方差，再用了别的文章的trick，可以重新参数化：

这个的证明应该不太难，搜了一下，当x服从N(μ, σ_2)，z=(x-μ)/σ，则z服从N(0, 1)，可以看到能推出上面那个新的P的式子。于是最小化目标公式再次更新：

这里，也就是多元标准正态分布。变了之后梯度就可以在q_unit中采样获取，更好求了。

这样就能用SGD解决了。作者附了个图证明这个方法有效，贴在下面，就不加赘述了。

集结一下最终算法。放这里：