##DeepWalkとは
DeepWalkとは、グラフの潜在的な特徴を得ることをモチベーションに、2014年に提案されたアルゴリズムです。
DeepWalkでは、無限次元で表現されるグラフの次元を削減し（埋め込み）、各ノードを有限次元のベクトルとして表現することをモチベーションとしています。
グラフの潜在的な特徴を得ることができると、ノードのクラスタリングやコミュニティ分類に活かすことができます。
それでは早速DeepWalkについて見ていきましょう！
##DeepWalk着想の背景
DeepWalkがなぜ考案されたのか、とても簡単にですがご紹介します。
###グラフ構造の不規則性
グラフに対して従来の機械学習アルゴリズムを適用することは、とても難しいことでした。
その理由として、グラフはそのままの定義でCNNを適用することができないことが挙げられます。
以下の図をご覧ください。
[A Comprehensive Survey on Graph Neural Networks](https://arxiv.org/pdf/1901.00596.pdf)より
(a)は画像に対する畳み込み、(b)はグラフに対する畳み込みを表しています。
画像の各ピクセルは規則的に並んでおり、隣接するピクセル数が一定であるのに対し、グラフは不規則な構造をしており、隣接するノード数も不規則です。これにより、CNNをそのまま適用することが難しかったのです。
###Word2Vecの発表
DeepWalkが発表される1年前の2013年、GoogleのTomas Mikolov氏らによって、Word2Vecというアルゴリズムが発表されました。
Word2Vecについてはこちらの記事で詳しく紹介されているので、ここでは簡単にWord2Vecのモチベーションをご紹介するにとどめます。
####分布仮説(Harris, 1954)
The Distributional Hypothesis is that words that occur in the same contexts tend to have similar meanings.
（詳しくはこちらを参照してください。）
Word2Vecは、Harrisの分布仮説に基づいて提唱されました。
一つの単語は複数の意味を持つことが当たり前で、最終的にその意味は周辺に出現した単語（文脈）によって決定される、ということをモチベーションとしています。
###グラフにも適用できないか？
自然言語とグラフ、両者に共通する点は、「離散値である」ということです。DeepWalkの提案者Bryan Perozzi氏らは、グラフもベクトルに落とし込んで（次元削減）、なんとかWord2Vecと同じような表現ができないかと考えました。
###ランダムウォーク
そこで考えられたのが、ランダムウォークを使ってグラフを文のように表すという考え方です。
ランダムウォークとは、ランダムに選んだノードを始点として、指定した長さになるまで隣接するノードに等確率で移動するという操作を繰り返します。
ランダムウォークで移動する過程で通ったノードを単語とみなし、ノードの集合を一つの文とします。
ランダムウォークにはマルコフ性がありますが、この辺の話はこちらをご覧ください。
[面白いデータを探して](https://netres-bigdata.hatenablog.com/entry/2018/07/06/042240)より引用
###Word2Vecに入力する
こうして得られた文（ランダムウォークで辿ったノードの集合）をWord2Vecに入力し、各ノードのベクトル表現を得ます。これが、グラフの潜在表現を獲得することができます。
##DeepWalk実装
今回は、NetworkXでサンプルデータとして用意されているKarate Clubのデータを使用して、DeepWalkを動かしてみます。
###Karate Clubデータセット
Zachary W.氏の論文『An Information Flow Model for Conflict and Fission in Small Groups』にて紹介されていたデータセットです。
- ある海外の大学で空手クラブで２人のリーダーが仲間割れしたときの内部の人間関係ネットワーク
- 空手部員をノード・交友関係をエッジとして表す
- ノードID = 33 (空手クラブの主将)とノードID = 0 (パートタイムのインストラクター)が空手クラブの経営問題を巡って対立した時の中心メンバー34人の友人関係を表す
- データに関するNetworkXのドキュメントはこちらを参照
今回は、対立後にパートナーの味方になった人を青、主将の味方になった人を赤で表現しています。
#randomwalkを実行する関数を定義
import matplotlib.pyplot as plt
import random
import networkx as nx
def make_random_walks(G, num_walk, length_of_walk):
#ランダムウォークで歩いたノードを入れるlistを生成
paths = list()
#ランダムウォークを擬似的に行う
for i in range(num_walk):
node_list = list(G.nodes())
for node in node_list:
now_node = node
#到達したノードを追加する用のリストを用意する
path = list()
path.append(str(now_node))
for j in range(length_of_walk):
#次に到達するノードを選択する
next_node = random.choice(list(G.neighbors(now_node)))
#リストに到達したノードをリストに追加する
path.append(str(next_node))
#今いるノードを「現在地」とする
now_node = next_node
#ランダムウォークしたノードをリストに追加
paths.append(path)
#訪れたノード群を返す
return paths
ランダムウォークで取得したノードをWord2Vecに入力します。
from gensim.models import Word2Vec as word2vec
G = nx.karate_club_graph()
#
walking = make_random_walks(G, 512, 512)
model = word2vec(walking, min_count = 1, size = 2, window = 10, workers = 1)
x = list()
y = list()
node_list = list()
colors = list()
fig, ax = plt.subplots()
for node in G.nodes:
#int型のままではイテレートできないので、string型に変換する
vector = model.wv[str(node)]
x.append(vector[0])
y.append(vector[1])
#注釈として、ノードの番号を追記する
#座標(x,y)は(vector[0],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()
当てはまりがいまいちですね。。
歩く歩数、１ノードあたり歩く回数をもう少し増やしてみましょう。
from gensim.models import Word2Vec as word2vec
G = nx.karate_club_graph()
walking = make_random_walks(G, 512, 512)
model = word2vec(walking, min_count = 1, size = 2, window = 10, workers = 1)
x = list()
y = list()
node_list = list()
colors = list()
fig, ax = plt.subplots()
for node in G.nodes:
#int型のままではイテレートできないので、string型に変換する
vector = model.wv[str(node)]
x.append(vector[0])
y.append(vector[1])
#注釈として、ノードの番号を追記する
#座標(x,y)は(vector[0],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()
いい感じにノードが分類されています！
##まとめ
今回は、グラフに自然言語処理の手法をアプローチを活用したDeepWalkをご紹介しました。
グラフと自然言語はもともとのデータ構造が似ており、関わりが深い分野だなと思っています。
是非とも試してみてください！
##参考
『面白いデータを探して』（大変参考にさせていただきました）
https://netres-bigdata.hatenablog.com/entry/2018/07/06/042240
DeepWalk: Online Learning of Social Representations（着想が見事でした）
https://arxiv.org/abs/1403.6652