Graph embedding の RESCAL [ICML'11] を実装した - でかいチーズをベーグルする

最近Graph embeddingに興味があって調べてるので有名っぽいRESCAL [ICML'11] をとりあえず実装してみた。さすが結構引用されてるだけあって簡単お手頃に実装できた。やっぱシンプルさ大事。

Graph embedding

入力

グラフ G = (V,E)

出力

それぞれの頂点 $v \in V$ に対して r次元ベクトルを１つずつ

要するにグラフ上の頂点の特徴を表す特徴ベクトルがほしいってこと。Representation learningとも言える。グラフ（上の頂点）をベクトル空間上に "埋め込む" からGraph embeddingと呼ばれている。この特徴ベクトルを使うことで普通のベクトルベースの機械学習手法をグラフにそのまま適用できるからうれしいねということになる。

RESCAL

ICML'11で提案されて、WWW'12でちょっと修正＆拡張されてちょっとでかめの実データで実験されてる。論文は以下。

RESCALは複数種類のエッジがあるグラフをembeddingする。複数種類のエッジがあるグラフっていうのはLODとかそういうやつ。最近の主流はこれで、DBPediaとかFreebaseとかYAGOとかのKnowledge graphをembeddingしたい人が多いらしい。

複数種類のエッジがあるグラフはテンソルで表現されるので、RESCALはテンソル分解ベースでembeddingをする。具体的には入力として与えられた n x n x m テンソルXに対して

${ \displaystyle X_k \approx AR_kA^{T} }$

という分解をする。ただし、 $X_k$ は n x n行列でテンソル X のk番目のfrontal slice（全部でm個ある）。また、Aは全てのkで共通。この n x r 行列 Aがembeddingの結果で、Aの各行がそれぞれの頂点の r次元ベクトルとなる。つまりテンソルXを復元できるような行列A（と行列Rk）を学習するという問題になる。基本的にはこれだけなんだけど詳細は論文をよんでね。

実装

お手軽簡単実装。ポイントはQR分解を使って目的関数に含まれる行列サイズを小さくするところと、クロネッカー積をうまいこと使うところかな。

gist3303398a61aa00f5707c

テスト

ICML'11の論文にある例（下の図）を使ってテストする。

f:id:yamaguchiyuto:20160214103156p:plain

著者的には (Bill, party, Party X) というトリプルが予測されてほしいらしい。果たして予測されるのか！？上のGistのコードを実行すると予測されたトリプルが出力される。

% python rescal.py
('Lyndon', 'vicePresidentOf', 'Bill')
('AI', 'vicePresidentOf', 'John')
('Bill', 'party', 'Party X')

確かに所望のトリプルは予測されたけど、余計なのも混じってる。まぁでも小さい例だしモデル上しょうがないのかな。

この例だけだと流石に小さすぎるので（気が向いたら）自分が公開してるTwitterリストのデータを使って試してみたい。

Following/Followers and Tags on 0.1 million Twitter Users - Zenodo

導出

書きたいけどちょっと力尽きた。気が向いたら。

まとめ

実装簡単。実行速い。精度はどうなんだろ*1。

*1:TransEの論文ではボロクソに書かれてた