agatan
commented
5 years ago 背景の簡単なまとめ
Graph Embedding ？
- グラフ構造は柔軟でいろんなデータを表すのに使えるし、グラフ構造上でなにかを予測したいみたいなタスクもたくさんある
- 一方で、グラフ構造を直接扱うのは結構難しいし、既存のアルゴリズムとの親和性が低い
- そこで、Graph Embedding で各ノードを固定長のベクトル表現に埋め込むことで、既存のアルゴリズムでも扱いやすい形でグラフを表現したい！
Applications
- Conversion をアイテム ↔ ユーザ の 2 部グラフだと考えて推薦に使う
- SNS 上における Link Prediction （知り合いですか？）
- Knowledge Graph の情報を他のタスクに応用しやすくする
DeepWalk
Graph Embedding 自体はめちゃくちゃいろんな手法が提案されている。 わかりやすくて簡単な DeepWalk について簡単にまとめると、
- Graph 上をたくさんランダムウォークする
[node1, node3, node8, node2, node9, ... ]をたくさん得る
- それぞれのランダムウォークを使って、word2vec と同じ要領で embedding を学習する
- それぞれのノードを単語とみなして word2vec にかける
というもの。 実装もめちゃくちゃ簡単だし、そこそこスケールする。 variant がたくさんある。
Knowledge Graph Embedding
(s, relation, d) の triple からなるエッジで構成されるグラフを扱いたい。
例: (モナリザ, was created by, ダ・ヴィンチ)
DeepWalk のような方法では relation を扱えない。
これもたくさんの手法が提案されているけど、一番わかりやすい方法は relation 自体にも embedding を定義した上で s + relation = d となるように学習する、という方法。
DKN: Deep Knowledge-Aware Network for News Recommendation は Knowledge Graph の情報を活用してニュースの推薦をしたいというストーリーで、Knowledge Graph Embedding を利用している。 Knowledge Graph はだいたい大規模なので、スケールする方法で埋め込みたい。 FB15K の場合は 14,951 entitiies, 1345 relations, 592,213 edges。
参考文献、他に読んだら面白いとおもうもの
- [1801.08284] DKN: Deep Knowledge-Aware Network for News Recommendation
- [1806.01973] Graph Convolutional Neural Networks for Web-Scale Recommender Systems
- benedekrozemberczki/Splitter: A Pytorch implementation of "Splitter: Learning Node Representations that Capture Multiple Social Contexts" (WWW 2019).
billion scale なグラフだと、 float32 x 128 次元の embedding を作ったらそれだけで 100 GB 単位のメモリが必要なのでやばいが、この論文ではそういうものも disk に書き出しつつ学習する方法を提案している。
グラフ使ってなんかするの、夢あるんだけどスケールさせるの大変だからなーと思ってた人いっぱいいると思う。 実際にはこの論文中で扱ってるグラフは1.2億ノードとかだし、心配するのはまだ早いのだけど、手元の貧弱な Mac Book Pro でも People のグラフ全体を簡単に扱えるとかはふつうに嬉しそう。
やっていること/えらいところ
sim(f(src, rel), f(dst, rel))を計算する感じf(src, rel) = srcLink Prediction で DeepWalk より良い精度を保ちつつ、billion scale なグラフでも学習できるようにした。