Graph Matching Networks for Learning the Similarity of Graph Structured Objects

https://arxiv.org/pdf/1904.12787.pdfを読む。

Contribution

GNNで1つのグラフを入力とし、similarity判定に使えるvectorを出力する方法
Graph Matching Networkと呼ばれる、入力は2つのグラフで、出力がそのsimilarity scoreのネットワークを提唱。Cross-graph attention mechanismというらしい。まあ要は2つのグラフ間でいろいろやっている。計算量は $O(n_1 n_2)$ なのでさすがにだいぶ遅いが、精度はかなりすごいらしい

Experiments

Synthetic graph edit-distanceを学習する
binary function similarity search
mesh retrieval (何これ)

Notes

Weihuaのやつはisomorphism testであってsimilarityではなさそう（WL kernel, similarity判定にはそれほど強くないのか？←Globalなsimilarityには確かに弱そう）
Related Workがおもしろい。Similarity basedなkernelがいくつか紹介されている。walks or paths (Borgwardt & Kriegel), limited-sized substructures (Horváth et al. 2004) , subtree (Shervashidze & Borgwardt 2009)など
kernelはhand-craftedなので大変だねという話
Metric Learningというのがあるらしい。2点間の距離を学習するらしい

Deep Graph Similarity Learning

Embedding models

要はベクトルを出力するモデル。事前に各グラフについてベクトル化しておくとクエリごとが楽。Encoder, Propagator, Aggregatorにわかれる。

f:id:xuzijian629:20190807053029p:plain f:id:xuzijian629:20190807053032p:plain

Encoder: 頂点ラベル（イテレーションごとに異なる）、辺ラベル（イテレーション間で同じ）を初期化

Propagator: $f_{message}$ とは、頂点 $j$ から頂点 $i$ へ向かう情報であり、2頂点のラベルと、辺ラベルでupdate。頂点ラベルは、その頂点のラベルとその頂点に向かうすべての頂点からのメッセージでupdate

Aggregator: $T$ イテレーションのあと、各ノードの特徴量をaggregateする。aggregateという単語ややこしいな

Graph Matching Networks

Embedding modelのpropagatorにおいて $f_{match}$ というのが増えた。2つのグラフの $2 n_1 n_2$ 個の組合せについて $f_{match}$ を計算する。ノードラベルのアップデートには、メッセージの他に、これらの情報を加えてアップデートする。 f:id:xuzijian629:20190807055128p:plain