DEEP GRAPH MATCHING CONSENSUS
2 Problem Definition
graph matching问题可以写为如下的quadratic problem
$$\arg \maxS \sum{i,j' \in Vs} \sum{j,j' \in Vt} A{i,i'}^{(s)} A{j,j'}^{(t)} S{i,j} S_{i',j'}$$
这个找寻的方法是基于neighborhood consensus：source graph中的neighbor node到了target graph中也应该比较靠近。（这个assumption在我们的例子里面不成立）
3 Method
我们的模型主要由两部分：local feature matching和iterative refinement strategy。
3.1 Local Feature Matching
首先通过GNN学到node representation $$H$$，然后两个图的soft correspondence可以通过内积加上sinkhorn normalization得到。sinkhorn normalization是说两个图的node尽量一一对应。
初始的loss就是对于每一个Source graph第i个节点到Target graph的negative log likelihood。
3.2 Synchoronous Message Passing for Neighborhood Consensus
因为学习node embedding是local的过程，我们的feature matching会偏向于找到的false correspondence会和ground truth在这个local structure上比较接近。这个例子就有可能违反了neighborhood consensus。找到global optimum是NP-hard的问题，所以我们试图在neighborhood中detect violations，然后用iterative的方法来解决它们。
我们用GNN来检测这些violations并iteratively refine correspondences。核心思路是：soft correspondence matrix $$S$$是从一个node function space到另外一个node function space的映射。因此，我们可以用$$S$$从一个node function （source/target）转移到另外一个node function （target/source）。
$$x_t' = S^T x_s, x_s' = S x_t$$
所以我们的consensus method就如下：将一个source graph上的indicator matrix映射到target graph。然后将coloring in corresponding neighborhoods通过synchronous message passing操作：
$$Os = f(I{Vs}, A_s, E_s), O_t=f(S^T{(l)} I_{V_t}, A_t, E_t)$$
用以上的结果能够得到任意source和target graph中的任意两个node相互之间的neighborhood consensus $$d_{i,j} = o_i^{(s)} - o_j^{(t)}$$。这个度量可以用了更新correspondence scores。
$$S{i,j}^{(l+1)} = \text{sinkhorn} (\hat S^{(l+1)}){i,j}$$, where $$\hat S^{(l+1)}{i,j} = \hat S^{(l)}{i,j} + \text{MLP} (d_{i,j})$$
最终的loss会将initial loss加上refined loss。
3.3 Releation to the Graduated Assignment Algorithm
一个类似的想法是graduated assignment algorithm。
$$S = \text{softassign}S \sum{i \in Vs} \sum{j \in Vt} Q{i,j} S{i,j}$$，其中 $$Q{i,j} = 2 \sum{i' \in V_s} \sum{j' \in Vj} A{i,i'}^{(s)} A{j,j'}^{(t)} S{i',j'} ^{l}$$
其中$$Q$$代表了公式1中的gradient。softassign就是通过sinkhorn normalization加上rescaled inputs。
3.4 Scaling to Large Input
结合算法的一些技术细节。
Appendix
感觉可以通过这种distribution difference来做一些事情。比如至少可以把这个和Wasserstein进行比较。