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