面白いデータを探して

適当に書く。間違えていたら教えてください。

DeepWalkを実装してみた

今回はgensimのWord2Vecを実際に使用して見たかったため、実際に実装してみました。
とはいっても、word2vecそのものや、sentence2vec、doc2vecのような言語系のプログラムはいろいろな方が実装していたので、今回はDeepWalk[1]というアルゴリズムを実装してみました。


DeepWalkとは

DeepWalkはGraph Embedding (Network Representation Learningとか呼ばれることもあります) の手法の一つです。
word2vecをグラフ構造に適応して、既存の手法よりも良い精度を発揮できたということで一躍有名になりました。

Graph Embedding

Graph Embeddin とは頂点と辺からなるグラフ構造を低次元のベクトル空間に落とし込むという分野です。
一般的には各頂点に1つのベクトルを対応させてベクトル空間に埋め込み(embedding)ます。
その際に、グラフ上でも近い/遠い頂点は近い/遠いベクトルを持つ、同じグループ(コミュニティ)に属するノードは密集して配置するといったようにネットワークの特徴をベクトル空間でも保持しているのがベストです。
イメージ的には下の図のようになるでしょうか。

f:id:netres:20180704105224p:plain

このように、グラフ構造をベクトルに変換することで、グラフ構造には用いることのできなかったk-meansやロジスティック回帰などを使うことができるようになります。
扱いにくかったグラフを扱いやすいベクトルにすることで、SNSやWEBページのようなビッグデータも扱いやすくなります。
例えば、twitterで言えば頂点が各ユーザーを、辺がフォローの関係を表していると考えることができ、これを分析することによって仲の良い人のグループの発見や、効果的なおすすめユーザーの紹介ができるようになります。

word2vec

word2vec[2]は文章を使って単語の関係をベクトル空間に埋め込むものです。
文章というのは、例えば「私は本を読む。」について、これを分かち書きした「私 は 本 を 読む」を使って学習を進めます。
たくさんの文章を使って学習を進めると、
妻 : (0.1, 0.2, 0.5)
夫 : (0.3, 0.3, 0.8)
王女 : (0.7, 0.7, 0.2)
王 : (0.9, 0.8, 0.5)
のような感じに各単語のベクトルを得ることができます。
また、このベクトルを使って「夫」-「妻」+「王女」=「王」のような単語の関係を使った計算もできるようになります。
word2vecの学習はskip-gramという手法を使っています。詳しい説明は他のページでも山ほどなされているのでここでは省きますが、重要なのは分かち書きした文章を使って学習するということです。
グラフ構造を分かち書きした文章と似たような表し方で表現することができれば、うまいことenbeddingができるかもしれません。

Random walk

そこで出てきたのがRandom walkです。
グラフの上を歩く人がいて、その人は頂点に着くと、その頂点とつながっているほかのノードにランダムに移動します。
このように移動して出来た列を文章と見なそうということです。

f:id:netres:20180706030104p:plain

これができてしまえば、あとはword2vecと同じように学習させればよいのです。

実装

概要

今回はKarate ClubというネットワークにDeepWalkを使ってみます。Karate Clubは文字通り空手クラブに通う人たち33人の関係を表したネットワークです。ネットワーク関係の論文などでは小規模な実験データとしてよく使われます。Karate Clubは下のような形のネットワークです。このKarate Clubは内部のいさかいののちに分裂してしまっており、青と赤は分裂後にどちらに所属したかを表しています。
f:id:netres:20180706032821p:plain

ソースコード

gensimは本題なのでいいとして、多くの人にとってnetworkxというのは使い慣れないライブラリかもしれません。networkxはグラフ構造を扱うためのライブラリで、python上でグラフ構造を利用する場合には非常に便利なライブラリです。

このプログラムではKarate Clubネットワークからrandom walkを生成、gensimのWord2Vecモデルで学習したのち、学習結果のベクトル空間を図示します。

また、多くの場合ではベクトル空間の次元は100程度ですが、今回は図示しやすいように2次元平面に埋め込みます。

# -*- coding:utf-8 -*-
import matplotlib.pyplot as plt
import networkx as nx
import random
from gensim.models import Word2Vec as word2vec

# Random Walk を生成するメソッド
# input:
# G Graph(networkx)
# num_of_walk それぞれの頂点から何本のwalkを作るか
# length_of_wake それぞれのwalkの長さ
# output: random walk
def make_random_walks(G, num_of_walk, length_of_walk):
  walks = list()
  for i in range(num_of_walk):
    node_list = list(G.nodes())
    for node in node_list:
      now_node = node
      walk = list()
      walk.append(str(node))
      for j in range(length_of_walk):
        next_node = random.choice(list(G.neighbors(now_node)))
        walk.append(str(next_node))
        now_node = node
      walks.append(walk)
  return walks

# 今回はKarate Clubというグラフを使用
G = nx.karate_club_graph()
# ランダムウォークを生成
walks = make_random_walks(G, 20, 20)
# gensim の Word2Vecを使った学習部分
model = word2vec(walks, min_count=0, size=2, window=5, workers=1)

# 可視化部分
# Karate Culubのそれぞれの頂点は2つのグループに分けられるので色分けして表示
x = list()
y = list()
node_list = list()
colors = list()
fig, ax = plt.subplots()
for node in G.nodes():
  vector = model.wv[str(node)]
  print("%s:"%(str(node)), end="")
  print(vector)
  x.append(vector[0])
  y.append(vector[1])
  ax.annotate(str(node), (vector[0], vector[1]))
  if G.node[node]["club"] == "Officer":
    colors.append("r")
  else:
    colors.append("b")
for i in range(len(x)):
  ax.scatter(x[i], y[i], c=colors[i])
plt.show()

実行結果は下のようになりました。
それなりに上手くいっているのではないでしょうか。

f:id:netres:20180706034038p:plain

ちょっと試してみる

とりあえず、ベクトル空間上の距離とグラフ上の距離との相関関係の散布図を書いてみましょう。頂点0について横軸がグラフ上の距離で、縦軸がベクトル空間上の距離を表す散布図です。

f:id:netres:20180706041751p:plain

グラフ上で近い点はベクトル空間上でも近く、遠い点は遠くと何となく配置されていることがわかります。

ほかの点につてもやってみましょう。

f:id:netres:20180706042012p:plain

ほかの点についても何となくうまくいっているように見えます。

まとめ

DeepWalkを実装してみて何となくうまくいきました。
今後はもう少し高次元の空間に埋め込んで、k-meansなんかを使ってクラスタリングをしてみたりします。
そのうち書きます。

その他

分布仮説とかRandom walkがエッジの分布をよく表現しているだとかそういった部分の話は省きました。
もっと細かく知りたい人は調べたほうがいいと思います。

参考

[1] Perozzi, Bryan, Rami Al-Rfou, and Steven Skiena. "Deepwalk: Online learning of social representations." Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014.
[2] Mikolov, Tomas, et al. "Efficient estimation of word representations in vector space." arXiv preprint arXiv:1301.3781 (2013).