[DL輪読会]Learning convolutional neural networks for graphs

Learning Convolutional Neural Networks for Graphs [ICML 2016 Niepert et. al.] 中山英樹研究室 横田 匡史

Introduction

概要 グラフ構造には様々なデータや形があり、それらを分類する のは難しい。そもそも同形性判定すら非常に難しい。

グラフ同形性判定問題はなぜ、 難しいのか？ 頂点番号に意味はないため、頂点番号に依存 しない特徴量が欲しい。

今回の論文の目的 ✦ 目的 • グラフをどうにかして処理したい • 同じような構造のグラフは同じ表現になって欲しい ✦ やったこと • WL Graph Kernelを応用しグラフ構造を前処理しCNN に突っ込めるようにした。

Related Work

グラフ類似判定アルゴリズム • Shortest-path Kernel • Random Walk Kernel • Graphlet Count Kernel • Weisfeiler-Lehman Kernel • 既存のグラフカーネルの中で最も性能が良い →この後、これがたくさん出てきます。

Weisfeiler-Lehman Graph Kernel 上記のような２つのグラフにWL Graph Kernelを使う

アルゴリズムの流れ 1. Multiset-label determination: 近傍のラベルを集めMulti Label Setを作成 2. Sorting each multiset: 集めたMulti Label Setをソート 3. Label compression: Multi Label Setを一つにまとめて、新しいラベルを作る 4. Relabeling: 各ノードに新しいラベルを割り当てる 5. 1〜4を指定回数 or Multi Label Setが変化しなくなるまで繰り返す。

Multiset-label determination このラベルから multiset label を作っていく

Multiset-label determination 隣接のラベルを 取ってくる

Multiset-label determination これをmultiset labelとする。

Multiset-label determination

Multiset-label determination

Multiset-label determination 上２つのグラフは、全てのノードに対して multiset labelを作ったもの。

Sorting each multiset 各ノードの multisetを ソートする

Label Compression 1,[4] 6 3,[2,4,5] 10 2,[3] 7 4,[1,1,3,5] 11 2,[3,5] 8 4,[1,2,3,5] 12 2,[4,5] 9 5,[2,3,4] 13 それぞれのmultisetに対して、新しいラベルを付ける。 (以後、この新しくつけたラベルをWLラベルと呼ぶ。)

Relabeling 新しくできたグラフに対して、指定回数もしくは グラフの関係が変わらなくなるまで行う。

グラフ作成後 各グラフのmultisetでのラベルをカウントし ベクトルを作り、内積を取ることで類似度を計る。

全体の流れ

PATCHY-SAN (提案手法)

Overview テンソル CNN 前処理 グラフに対して、WLを応用しテンソルを得る。 それをCNNに入れてクラス分類を行う。 出力

PATCHY-SANの流れ 1. Weisfeiler-Lehman Graph Kernel で新しくラベルを付 ける。 2. WLのラベルでノードをソートしw個選ぶ 3. 各ノードに対して近いノードをk個以上選ぶ 4. ステップ3で選んだノードをソート・選択する 5. 選んだノードを並べてテンソルを作る。

ステップ1 グラフカーネルで新しくラベルを付ける WL Graph Kernel これを使って ノードを選んでいく

ステップ2 WLラベルでノードをソートし、w個選ぶ w=4として左のグラフから 頂点ラベルを選んでいく。 [グラフの頂点リスト] 6, 7, 9,10,12,13 最終的に選んだ ４個のラベルを ステップ3に移す 6, 7, 9, 10

ステップ3 各ノードに対して近いノードをk個以上選ぶ ステップ2で選んだノードについて 1. あるノードvに対して、距離１のノードが|N|≧kなら終了 2. あるノードvに対して、距離２のノードが|N|≧kなら終了 3. …以下、|N|≧kになるまで繰り返し… ラベル6のノードについて 距離1：6→12 距離2：6→12,9,13,10 これを先に選んだw個のラベル について行う。

ステップ4 ステップ3で選んだノードをソート・選択する 1. 頂点からの距離でソート 2. 距離が同じならWLラベルでソート 3. ソート後の配列からtop-kを選択する ラベル6のノードについて 距離でソート 6→12,9,13,10 WLラベルでソート 6→12,9,10,13

ステップ5 選んだノードを並べてテンソルを作る • • • 縦にw個のノード(ステップ2) 横にk個のノード(ステップ3,4) 各頂点の持つ属性をa次元ベクトルとして、 (w, k, a)のテンソルを作る。 これにより作成したテンソルを CNNに入力し、グラフのクラス分類を行う

PATCHY-SANの流れ 1. Weisfeiler-Lehman Graph Kernel で新しくラベルを付 ける。 2. WLのラベルでノードをソートしw個選ぶ 3. 各ノードに対して近いノードをk個以上選ぶ 4. ステップ3で選んだノードをソート・選択する 5. 選んだノードを並べてテンソルを作る。

PATCHY-SANのメリット ★ 属性に離散値・連続値のどちらでも使える ‣ これは非常に重要らしい ‣ 先行研究で連続値も扱えるカーネルは精度が劣っていた ★ 辺属性も同時に用いることができる ‣ 頂点属性のときにk個属性を並べた代わりに 隣接行列のようにk^2個の属性を並べる ★ 最初のラベル付けのアルゴリズムは何でも良い (WL graph kernelが絶対ではない) ‣ 類似するノード同士が近い値を取るようなアルゴリズムならばなん でも良い。

実験

実験条件 • 比較アルゴリズム 1. Shortest-path Kernel 2. Random Walk Kernel 3. Graphlet Count Kernel 4. Weisfeiler-Lehman Kernel 5. LIB-SVM 6. PATCHY-SAN(提案手法) • 使用データセット • MUTAG,PCT,NCI1,NCI109→化学化合物 • PROTEIN,D&D →タンパク質(3D構造)

提案手法での使用モデル • モデルへの入力 ‣ PATCH-SANによってできた(w, k, a)のテンソルを(wk, a) にreshapeしたもの • 使用モデル ‣ w = 平均頂点数, k=5, 10 ‣ Conv → Conv → FC → Softmax ‣ Convはfilter sizeとstrideを それぞれkとした1D Convolutionである。

実験結果 (PSLR: PACHY-SAN+Regression) 全体的にPATCHY-SAN+CNNの手法が精度的にも 速度的にも早くなっている。

所感 • ほとんど前処理の話だけだが、アルゴリズムも簡単で 良さそう。 • Visual Genomeや構文木などをこれに使うと面白そう ‣ 特にWL Graph Kernelの代わりにGloveとかを使って別 のラベル付けの仕方とかできそう(適当)

参考 • Learning Convolutional Neural Networks for Graphs(PFNの秋葉 さんのslide share) ‣ http://www.slideshare.net/iwiwi/learning-convolutionalneural-networks-for-graphs-64231265 ‣ グラフ界隈の話は初めてだったので、かなりお世話にな りました。

• http://www.slideshare.net/iwiwi/learning-convolutional-neural-networks-for-graphs-64231265