Finding Matches in a Haystack: A Max-Pooling Strategy for Graph Matching in the Presence of Outliers

Minsu Cho, etc.

Intro

该应用是在有非常多的outlier node情况下进行graph mapping。

Standard formulation: 根据paper中的定义，我们可以得到

$$f(X) = \sum{x{ia}=1, x{jb}=1} s_E(e{ij}, e'{ab}) + \sum{x_{ia}=1}s_V(v_i, v'_a)$$

而后通过一个巧妙的构造，令$$x\in \mathbb{R}^{nn' \times 1}$$为$$X$$列向量的vectorize，而$$A{ia;jb}=s_E(e{ji}, e'{ab})$$当$$ia \ne jb$$，否则$$A{ia;ia}=s_V(v_i, v'_a)$$。

从而有$$f(X) = x^T A x$$。

不难发现这是一个integer quadratic optimization问题。

Max-Pooling for matching: 用泰勒极限逼近

$$f(x) \approx f(x_k) + (x - x_k)^T A x_k$$

然后是公式(3)推导到公式(4)。在一阶优化的框架下，优化$$x^T A x_k$$会有

Then by the Raleigh’s ratio theorem, $$x^∗$$ that will maximize the inter-cluster score $$x^TMx$$ is the principal eigenvector of M.

而最大的特征值可以根据power iteration求解

$$x_{k+1} = \frac {1}{|Ax_k|_2} A x_k$$

从直观上理解公式5，$$(Ax)_{ia}$$。然后提出了这里的$$Ax$$类似于sum-pool操作，而会由于无关node的信息太多带来问题。因此提出使用max-pool代替sum-pool。

关于power method，再提几点

如果$$A$$是对称，那么$$A = Q ^{-1} \bigwedge Q$$，其中$$Q$$是orthogonal，$$\bigwedge$$是diag。

$$A^k = Q \bigwedge^k Q^T$$

$$x_1 = A x_0$$ $$x_k = A^k x_0$$