はじめに

Deep Learning of Graph Matchingを読んだのでメモ．タイトルの通り，graph matchingの問題をdeep learningで解くと言うもの．

Graph Matching

まずgraph matchingの定式化から入る．二つのグラフ $\mathcal{g}_1=(V_1,E_1),\mathcal{g}_2=(V_2,E_2)$ が与えられたとする．ただし， $|V_1|=n,|V_2|=m$ とする．graph matchingの目的はこの二つのグラフのノード間の最適な対応関係を作ること．

$\mathbf{v}\in\{0,1\}^{nm\times 1}$ を， $i\in V_1$ と $a\in V_2$ が対応する場合 $\mathbf{v}_{ia}=1$ ，それ以外を0とする指示ベクトルとする．さらに二組みのエッジ， $(i,j)\in E_1, (a,b)\in E_2$ がどれくらい対応(類似)しているかを $\mathbf{M}_{ia;jb}$ 成分に持つ行列 $\mathbf{M}\in\mathbb{R}^{nm\times nm}$ を定義する．ただし，この行列 $\mathbf{M}$ は対角成分に $\mathbf{v}_{ia}$ を持つ．すなわち $\mathbf{M}$ はノードの対応関係とエッジの対応関係を記述した行列となる．論文の言葉を使えば，対角成分はunaryで非対角成分はpair-wiseのスコアを記述する．この行列 $\mathbf{M}$ を使えば最適な割り当て $\mathbf{v}^\ast$ は次のように定式化される．

$\displaystyle \mathbf{v}^\ast=\mathrm{argmax}_{\mathbf{v}}\mathbf{v}^\top\mathbf{Mv},\:\mathrm{s.t.}\:\mathbf{Cv}=\mathbf{1},\:\mathbf{v}\in\{0,1\}^{nm\times 1}$

ここで $\mathbf{C}\in\mathbb{R}^{nm\times nm}$ は2値の行列で， $\forall a\sum_i\mathbf{v}_{ia}=1,\forall i\sum_{a}\mathbf{v}_{ia}=1$ と言う二つの写像を表す．この問題はNP-hardということが知られているため，次のように緩和する．

$\displaystyle \mathbf{v}^\ast=\mathrm{argmax}_{\mathbf{v}}\mathbf{v}^\top\mathbf{Mv},\:\mathrm{s.t.}\:\|\mathbf{v}\|_2=1$

この問題は $\mathbf{M}$ の各要素が非負かつ $\mathbf{M}$ が正方行列であることからPerron-Frobeniusの定理から $\mathbf{M}$ の最大固有値の固有ベクトルとして解が与えられる．Perron-Frobeniusの定理は簡単に言えば，各要素が非負の正方行列の最大固有値は重複度1で，その固有ベクトルは各成分が正になるというもの．上記の緩和により $\mathbf{v}\in[0,1]$ であるため通常の固有値問題ではこの制約を満たせないが，Perron-Frobeniusの定理から得られる最大固有値の固有ベクトルは $[0,1]$ であることが保証されることにより，固有値問題として解くことが可能になるというもの．

この論文の目標はこのgraph matching問題を学習ベースで解くことで，言い換えれば真の対応関係を記述する $\mathbf{M}$ をparameterizeするというもの．

Affinity Matrix Factorization

この論文で重要となる $\mathbf{M}$ の表現方法．ここでは2012年のCVPRで提案されたFactorized Graph Matchingを使う．Factorized Graph Matchingはunary scoreとpair-wise scoreを別々に表現できるように（という解釈で合ってるかは微妙だが） $\mathbf{M}$ を分解する．

$\displaystyle \mathbf{M}=[\mathrm{vec}(\mathbf{M}_p)]+(\mathbf{G}_2\otimes\mathbf{G}_1)[\mathrm{vec}(\mathbf{M}_e)](\mathbf{H}_2\otimes\mathbf{H}_1)^\top$

$[\mathbf{x}]は[tex:\mathbf{x}$ を対角成分とする対角行列を表し， $\otimes$ はクロネッカー積を表す． $\mathbf{M}_p\in\mathbb{R}^{n\times m},\mathbf{M}_e\in\mathbb{R}^{p\times q}$ はそれぞれunary score（ノード間のスコア）とpair-wise score（エッジ間のスコア）を表す行列で， $\mathbf{G},\mathbf{H}\in\{0,1\}^{n\times p}$ は $c$ 番目のエッジが $i$ のノードから $j$ のノードに入る場合 $g_{ic}=h_{jc}=1$ となる行列で， $p,q$ をエッジの数とすれば $\{\mathbf{G}_1,\mathbf{H}_1\}\in\{0,1\}^{n\times p},\{\mathbf{G}_2,\mathbf{H}_2\}\in\{0,1\}^{m\times q}$ となる．なので上の分解表現における $\mathbf{G}$ と $\mathbf{H}$ のクロネッカー積の項は $nm\times pq$ 行列となり， $[\mathrm{vec}(\mathbf{M}_e)]$ は $pq\times pq$ 行列となる． $\mathbf{G},\mathbf{H}$ のクロネッカー積を $[\mathrm{vec}(\mathbf{M}_e)]$ にかける意味としては， $\mathbf{M}_{ia;ib}$ 要素が $(i,j),(a,b)$ のエッジ間のスコアと対応付くようにするということ．

$\mathbf{M}_e,\mathbf{M}_p$ の単純な構成方法としては次のようなものが考えられる．

$\displaystyle \mathbf{M}_e=\mathbf{X\Lambda Y}^\top,\:\mathbf{M}_p=\mathbf{U}^1\mathbf{U}^{2\top}$

$\mathbf{X}\in\mathbb{R}^{p\times 2d},\mathbf{Y}\in{\mathbb{R}^{q\times 2d}}$ はエッジごとの特徴量を要素に持つ行列で， $\mathbf{U}^1\in\mathbb{R}^{n\times d},\mathbf{U}^2\in\mathbb{R}^{m\times d}$ はノードごとの特徴量を要素に持つ行列． $\mathbf{\Lambda}$ はブロック対称行列でおそらく学習パラメータ．エッジの特徴量を記述した行列 $\mathbf{X},\mathbf{Y}$ はエッジによって結ばれる二つのノードの特徴量 $\mathbf{F}_1\in\mathbb{R}^{n\times d},\mathbf{F}_2\in\mathbb{R}^{m\times d}$ を使って次のように記述する．

$\displaystyle \mathbf{X}_c=[\mathbf{F}_i^1|\mathbf{F}_j^1],\mathbf{Y}_c=[\mathbf{F}^2_i|\mathbf{F}_j^2]$

$\mathbf{F},\mathbf{U}$ の違いは，グラフの特徴表現を得る埋め込みモデル（多層のニューラルネットを仮定）の異なる層から得られる特徴とのこと．上付きの数字，1と2はグラフの種類．

Deep Network Optimization for Graph Matching

ここから具体的なアルゴリズムの話．構成としては

Deep Feature Extractor（今回は2枚の画像を入力として想定しているため，個別にVGG-16で特徴抽出）
Affinity Matrix
Power Iteration
Bi-Stochastic
Voting
Loss

からなる（論文のFigure 1参照）．

Affinity Matrix

ノード間のエッジの有無を表す隣接行列が各グラフごとに $\mathbf{A}_1\in\{0,1\}^{n\times n},\mathbf{A}_2\in\{0,1\}^{m\times m}$ として定義されているとする．するとそれぞれ以下のような関係が成り立つ．

$\displaystyle \mathbf{A}_1=\mathbf{G}_1\mathbf{H}_1^\top,\:\mathbf{A}_2=\mathbf{G}_2\mathbf{H}_2^\top$

つまり隣接行列が与えられれば $\mathbf{G},\mathbf{H}$ が得られる（分解方法は非自明だが $\mathbf{G},\mathbf{H}$ はノード・エッジ間の関係なので，行列分解によって計算するというより解析的に計算可能）． $\mathbf{G},\mathbf{H}$ が得られれば前段のfeature extractorから得られた特徴行列を用いて，Factorized Graph Matchingの関係から $\mathbf{M}$ を作ることが可能．forward, backward計算の詳細な計算は割愛．

Power Iteration Layer

最適な割り当て $\mathbf{v}^\ast$ を得るためには $\mathbf{M}$ の最大固有値の固有ベクトルを計算すればいいが，固有値分解はコストが高いためここでは以下のようにPower Iterationで計算する．

$\displaystyle \mathbf{v}_{k+1}=\frac{\mathbf{Mv}_k}{\|\mathbf{Mv}_k\|_2}$

ただし初期値は $\mathbf{v}_0=\mathbf{1}$ とする．iteration数 $N$ はハイパラ．backwardの詳細は割愛（ただし計算オーダーを落とすための工夫が所々あるので要参照）．

Bi-Stochastic Layer

Graph matchingの解としては $\forall a,\sum_i\mathbf{v}_{ia}=1,\forall i,\sum_a\mathbf{v}_{ia}=1$ という二重確率を満たす必要がある．ここでは $\mathbf{v}^\ast\in\mathbb{R}^{nm\times 1}_+$ を入力として $n\times m$ の二重確率行列 $\mathbf{S}$ を出力するBi-Stochastic Layerを提案する．

初期行列 $\mathbf{S}_0=(\mathbf{v}^\ast)_{n\times m}$ が与えられたとし，以下の繰り返し計算を行う．

$\displaystyle \mathbf{S}_{k+1}=\mathbf{S}_k[\mathbf{1}_n^\top\mathbf{S}_k]^{-1},\:\mathbf{S}_{k+2}=[\mathbf{S}_{k+1}\mathbf{1}_m]^{-1}\mathbf{S}_{k+1}$

このiterationの元を辿ったところ，これは $\forall a,\sum_i\mathbf{v}_{ia}=1,\forall i,\sum_a\mathbf{v}_{ia}=1$ を満たさないが， $\mathbf{S1}_{m}=\mathbf{1}_n,\mathbf{1}_n^\top\mathbf{S}=(n/m)\mathbf{1}_n$ が成り立つらしい(もしかしたら参考にした論文と多少違いがあるかもしれないので要出展)．

Converting Confidence-maps to Displacements

最後に $\mathbf{S}\in\mathbb{R}^{n\times m}$ からdisplacement vectorを得る．これは正規化をしたいということらしく，割り当てられた点 $i$ が $\mathbf{S}$ の $i$ 行目で与えられたスコアと一致するようにしたいということらしいが，イマイチよくわからない．なので以下は殴り書き．the matrix of positions $\mathbf{P}\in\mathbb{R}^{m\times 2}$ という行列を用意して，対応する点 $i$ の位置との差を使って以下のようにdisplacement vectorを得るとのこと．