KDD 2018 | Graph Convolutional Neural Networks for Web-Scale Recommender Systems
著者に Jure Keskovec がいる．
Pinterest における推薦にて node の embedding を graph convolution で学習する推薦手法 PinSage を提案している．タイトルだけ読むとそのように思えるけれど，実際には Graph Convolutional Network で行われるような Graph Fourier変換にもとづく畳み込みを行っていない．この点を誤解しているまたはまともに読んでない人しかいないのではないかと思う (footnote 1 で however, the architecture we employ does not directly approximate a spectral graph convolution と言及もしている)．
PinSage における Graph Convolution
Convolution
今，次のような関数を考える (論文中ではこの操作を Convolution と呼んでいる)．論文中の Algorithm 1 の説明では と
が未定義の状態で登場していて完全に意味不明なので論文の主張に沿って正しいと思われるコードを書く．
# node u に対する畳込みを得る関数 # z_u : u の現在の畳み込み表現 # z_neighbors : u の近傍ノードの畳み込み表現の集合 # alpha : 近傍ノードの重み # Q, q : importance_pooling に渡す前のパラメタ # W, w : 最後の ReLU に渡す前のパラメタ def covolve(u, z_u, z_neighbors, alpha): n_u = importance_pooling(ReLU(Q * z_neighbors + q), alpha) z_u_new = ReLU(W * concat(z_u, n_u) + w) return normalize(z_u_new) # vectors を element-wise に weights で重み付けして平均を取る pooling 関数 def importance_pooling(vectors, weights): i, j = vectors.shape ret = [ ] for dim in j: ret[dim] = np.mean(vectors[dim, pos] * weights[pos] for pos in range(i)) return ret
何をやっているかというと，ある node に対する embedding をその近傍にある node の embedding をまとめて pooling し，現在の embedding と concat した上で ReLU に通している．これを深さ
まで繰り返し適用する (論文中では
回目の繰り返しにて得られる embedding を
と表現している)．思ったよりシンプル．
ここだけ読むとシンプルな話でいいわけですが，論文冒頭では「 node には visual や texual な feature が付与されている」「この手法ではそれら feature を使って embedding を学習する」と書いてある．しかし上記のコードにはそれら feature に対する言及がない．"We start with input node features and then learn neural networks that transform and aggregate features over the graph to compute the node embeddings" と書いてはあるがその後の記述を読むと embedding のことを feature と呼んでいて正直に言って全く理解できない．
id:another16javac さんから「GraphSAGE [1706.02216] Inductive Representation Learning on Large Graphs が参考になる」というコメントをいただき読んだところ を特徴量
で初期化しているのでここで使うという話だった．そしてこの論文もよく読むと algorithm 2 で同様に
を
で初期化していた．恥ずかしい．
細かいテクニック
- Pixie で行ったように
から始まるランダムウォークによる訪問回数が上位の node を近傍として用いる．また，この時の訪問回数を重み
として用いる． Pixie ではこの時のランダムウォークに用いる遷移行列を node の特徴量を謎の関数に通して重み付けしていたが，まさかこれが上記の疑問に相当する?
- 学習はクエリ
と正例
のペア
が与えられていると考え，負例のペアより正例のペアの embedding の内積が大きくなるように学習する．
- またこの時，負例は negative sampling するわけですが uniform にやるとほとんど関係ない負例ばかり出てきて関数が収束しない．そこで
- 学習は MapReduce． d2.8xlarge のインスタンスを 378 台並べてクラスタを作る．
Graph の convolve は分かるけどどうやって特徴量を有効活用したのかわからない．
