【動画講座】Jure Leskovec "Deep Learning on Graphs"

リンク

https://www.youtube.com/watch?v=MIAbDNAxChI

画像

内容

ML on Graphs

グラフが与えられたとき、グラフからラベルを予測したい。

たとえば

  • ある2頂点間にエッジはあるか?
  • PageRankはいくつか?
  • 字数はなんこか?

などである。

DeepLearnings on Graphs

しかし、このままだと頂点数や計算量で難しいため
CNNのConvolutionのアイディアを利用する。

これによって、予測をおこなう。

特徴量学習

グラフを元に、$R^d$という特徴量を見つけて学習することが目的。

Embeddings

文字や単語・文などの構成要素を、何らかの空間のベクトルにすることをEmbeddingという。

たとえば、CountVectorizerも単語のベクトル化をしている。
これによって、ベクトルに置き換えて扱いやすくし、特徴量とする。

Graph SAGE

GraphSAGEはGraph Convolution Networkの一つ。
うまいこと予測できる。

Determinant Invariant

決定的不変性。

$f:R^n{\to}R^m$
という関数を考えるとき、$f$の入力の順序が異なっても出力が同じなら$f$はDetermine Invariantという。

例えば、max, avgはそうである。

計算グラフ

SAGEのアイディア。
各頂点から、各頂点を根とした計算グラフを作る。
これをつかって、情報を集約していく。

変数

$h_A^{(k)}$は、メッセージ$h$で、頂点$A$のレイヤー$k$での
メッセージである。

これを周辺から集めて以前の自分$h_A^{k-1}$と、周辺の値と合計を取る。

aggrigation(集約)と合計(sum)は異なる意味で使用されているため注意。

aggigationは、平均や合計など、出力が一意に定まるなら何でもいい。

パラメータ共有

各計算グラフで、重みを共有するらしい。
共有することで、新しいグラフが来ても、その共有された重みを使用することで
推測することができる。