Graph Neural Networks
はじめに
私自身グラフ理論や計算機科学といった分野に精通している人間ではないので定義や解釈が厳密ではない可能性があります.
また論文等でよく出てくる単語に関しては英語表記のまま記述しています.
あくまで機械学習としてのGraph Neural Networkを理解するための解釈をしています.
そもそもGraphとは
ざっくり理解
graph構造のデータとしてよく挙げられるのがSNSのユーザ間のつながりや論文の引用関係,タンパク質の構造などたくさんあるが,重要なのは ある点とある点の関係を線で結んで表現できる構造である ということだ.
簡単のために相互フォローであり,関係性に方向はない(無向グラフ)としてSNSのつながりを表現するとFig.1のようになる.
Fig.1 SNSのユーザ間のつながり
このユーザーをnode
より具体的に
Fig.1でSNSのユーザー間の繋がりを例に挙げたのでこれを深掘りしていく.
Step 1 Edgeをmatrixで表現する
まず,図のままだと数学的・プログラミング的に扱いにくいのでmatrixで表現していく.
つながりを表現するときに用いられるのがadjacency matrixである.
このmatrixは
例えば,AとBは繋がっているので
これを図で表現するとFig.2のようになる.
Fig.2 adjacency matrix
Step 2 Nodeをmatrix表現する
ユーザーが無個性な訳がないので普通はnodeも特徴を持っている.
ここでは例として以下のような属性を付与してみる.
- 趣味のジャンル(0-1): 趣味に費やす時間のうち,運動,芸術,ゲームの割合を示す.合計で1になるように割り当てる
- スポーツが好きか(0 or 1): スポーツが好きなら,そうでないなら0
特徴を増やしすぎてもややこしくなるのでこの程度でおさめておく.このような特徴を格納した配列をfeature matrixといい,特徴の数を とするとd の行列N \times d として表現される.このgraph全体のfeature matrixはFig.3のように表される.\mathbf{X}
Fig.3 feature matrix
この章のまとめ
- graphというのはnodeとedgeで構成される情報のこと.
- nodeとedgeにはそれぞれ情報があり,それらはmatrixで表現される.
Graph Neural Network
Graph Convolutional network
Graph Neural Networkで最も一般的に用いられる手法がGraph Convolutionalである.
これは基本的には画像のConvolutionalと同じで近傍の特徴に重みを掛け合わせて特徴を集約するといった手法である.
画像と違う点は大きく以下の2点である.
- node間に位置の関係がない
- 中心のnode自身の特徴の扱いが違う
1. node間に位置の関係がない
画像では画素の位置を考慮してたたみ込んでいる.例えばFig.4のように
Fig.4 convolution for image
一方グラフでは,FIg.5のようにBさんからみてAもDもEもただのSNSのフォロワーであり,そこに区別はない.そのため画像のようにそれぞれに対応した3つの重み(B-A,B-D,B-E)で畳み込むのではなく,共通の1つの重みで畳み込む.
ここで
Fig.5 graphの畳み込み
2. 中心のnode自身の特徴の扱いが違う
中心のnodeについては大きく2通りの方法があり,近接nodeと同じ重みで畳み込む方法と独立した重みで畳み込む方法がある.
同じ重みで畳み込む場合
独立した重みで畳み込む場合は以下のように定義する.
Fig.6 中心node自身の畳み込み
matrixを使って表現すると
説明が簡単なので,中心nodeを近接nodeと同じ重みで畳み込む場合で説明していく.
中心nodeが近接nodeと同じということはadjacency matrixの対格成分(self-loop)が追加されるのと同義である.よって
簡単のため
Normalize
画像の畳み込みは常に畳み込む数が同じだが,graphの場合はそうもいかない.Fig.1のようにAさんは2つ,Bさんは3つ,Cさんは1つのnodeとつながっているように,nodeによって隣接nodeの数が様々である.そこでつながっているnodeの数で割ることによって正則化を行う.
この数式の
Fig.7 degree matrixによる正則化
よって
ただし,この正則化方法も論文によって様々提案されており,Semi-Supervised Classification with Graph Convolutional Networksという論文では以下のような形状で提案されている.
そしてこの
この章のまとめ
- 基本的にはCNNと考え方は同じ
- graphの特性(位置情報がない,中心nodeと近傍node)に合わせた拡張がされている
- nodeによって畳み込む数が違うので正規化されている
最後に
最近話題のGraph Neural Neteworkについて自分なりにまとめてみました.
比較的新しい手法であることもあり,日本語の記事が少なく理解に苦しんだのでこの記事が誰かの理解の手助けになれば幸いです.
Discussion