古典ランダムウォーク（DeepWalkとNode2Vec）

概要

この記事では、「古典ランダムウォーク（DeepWalkとNode2Vec）」の定義や性質、応用例について詳しく説明する。ランダムウォークを用いたグラフ埋め込み手法であるDeepWalkとNode2Vecの数学的背景、アルゴリズムの詳細、具体的なPythonコードによる実装例を通じて、推薦システムなどでの利用例やメリット・デメリットを解説する。

ソースコード

github

jupyter notebook形式のファイルはこちら

google colaboratory

google colaboratory で実行する場合はこちら

実行環境

OSはmacOSである。LinuxやUnixのコマンドとはオプションが異なることに注意。

!sw_vers

ProductName:		macOS
ProductVersion:		13.5.1
BuildVersion:		22G90

!python -V

Python 3.9.17

pandasのテーブルを見やすいようにHTMLのテーブルにCSSの設定を行う。

基本的なライブラリをインポートし watermark を利用してそのバージョンを確認する。ついでに乱数のseedの設定を行う。

%matplotlib inline
%config InlineBackend.figure_format = 'svg'

import random

import scipy
import numpy as np

import matplotlib
import matplotlib.pyplot as plt

seed = 123
random_state = 123

random.seed(seed)
np.random.seed(seed)

from watermark import watermark

print(watermark(python=True, watermark=True, iversions=True, globals_=globals()))

Python implementation: CPython
Python version       : 3.9.17
IPython version      : 8.17.2

numpy     : 1.25.2
matplotlib: 3.8.1
scipy     : 1.11.2

Watermark: 2.4.3

古典ランダムウォークとは

定義

古典ランダムウォークとは、グラフ理論におけるランダムウォークの一種である。グラフ上のノードからスタートし、ランダムに隣接ノードへと移動するプロセスを繰り返すものである。このプロセスは確率的であり、次のノードへの移動はランダムに決定される。

ランダムウォークの確率行列 $\mathbf{P}$ は次のように定義される：

$$ \mathbf{P}_{ij} = \begin{cases} \frac{1}{d_i} & \text{if } (i, j) \in E \\ 0 & \text{otherwise} \end{cases} $$

ここで、$d_i$ はノード $i$ の次数である。

性質

エルゴード性：十分な長さのランダムウォークはグラフ全体をカバーする。
定常分布：長い時間をかけると、ランダムウォークは定常分布に収束する。
マルコフ性：現在の状態のみが次の状態に依存し、過去の状態には依存しない。

DeepWalk

定義

DeepWalkは、グラフ内のノードをランダムウォークに基づいて学習する手法である。具体的には、グラフ上でランダムウォークを行い、その結果得られたノードシーケンスを用いて、Skip-gramモデルでノードの埋め込みを学習する。

アルゴリズム

ランダムウォークの生成：各ノードからスタートし、ランダムに隣接ノードへ移動するウォークを複数生成する。
Skip-gramモデルの学習：生成されたノードシーケンスを入力として、Skip-gramモデルを用いてノードの埋め込みを学習する。

$$ J = - \sum_{w \in V} \sum_{u \in N(w)} \log P(u|w) $$

Pythonによる実装例

以下に、DeepWalkの基本的な実装例を示す：

データとして、networkxに標準で搭載されているkarate_club_graphを使用する。

import numpy as np
import networkx as nx

from pprint import pprint

from gensim.models import Word2Vec


def random_walk(graph, start_node, walk_length):
    walk_list = [start_node]
    for _ in range(walk_length - 1):
        neighbor_list = list(graph.neighbors(walk_list[-1]))
        if neighbor_list:
            walk_list.append(np.random.choice(neighbor_list))
        else:
            break
    return walk_list


def generate_walk_list(graph, num_walk_list, walk_length):
    walk_list = []
    node_list = list(graph.nodes())
    for _ in range(num_walk_list):
        np.random.shuffle(node_list)
        for node in node_list:
            walk_list.append(random_walk(graph, node, walk_length))
    return walk_list


# グラフの作成
G = nx.karate_club_graph()

# ランダムウォークの生成
num_walks = 10
walk_length = 5
walks = generate_walk_list(G, num_walks, walk_length)

# Skip-gramモデルでの学習
model = Word2Vec(walks, vector_size=64, window=5, min_count=0, sg=1)

# ノードの埋め込みを表示
embeddings = {node: model.wv[node] for node in G.nodes()}

# 最初のノードだけ学習結果を表示
pprint(embeddings[0].round(4))

array([ 0.0003,  0.0038,  0.0068,  0.0115, -0.0065, -0.0014,  0.0095,
        0.0189, -0.002 , -0.0164,  0.0105, -0.0006,  0.0142, -0.0015,
       -0.0071, -0.0128, -0.0034,  0.0057,  0.0067,  0.0124, -0.0037,
        0.0052,  0.0179, -0.0091, -0.0047,  0.0161, -0.0006,  0.0006,
        0.0049, -0.0007,  0.0136,  0.0106, -0.0222, -0.0166,  0.0024,
        0.0117, -0.0107,  0.011 ,  0.0167,  0.0078,  0.0132, -0.0059,
        0.0016,  0.0041, -0.004 , -0.0126, -0.0022, -0.0154, -0.0094,
        0.0114,  0.0081,  0.0115,  0.0103,  0.018 ,  0.0006,  0.0024,
        0.0083, -0.0101,  0.0099, -0.0185,  0.012 ,  0.0013, -0.0087,
        0.008 ], dtype=float32)

Node2Vec

定義

Node2Vecは、DeepWalkを拡張した手法であり、ランダムウォークにおいて深さ優先探索（DFS）と幅優先探索（BFS）をバランス良く組み合わせることで、ノードの埋め込みを学習する。

アルゴリズム

ランダムウォークの生成：DFSとBFSのバランスを調整するためのパラメータ $p$ と $q$ を導入し、ランダムウォークを生成する。
Skip-gramモデルの学習：DeepWalkと同様に、生成されたノードシーケンスを入力として、Skip-gramモデルでノードの埋め込みを学習する。

$$ J = - \sum_{w \in V} \sum_{u \in N(w)} \log P(u|w) $$

Pythonによる実装例

以下に、Node2Vecの基本的な実装例を示す：

こちらもデータとして、networkxに標準で搭載されているkarate_club_graphを使用する。

import numpy as np
import networkx as nx

from pprint import pprint

from gensim.models import Word2Vec


class Node2Vec:
    def __init__(self, graph, p, q, num_walk_list, walk_length):
        self.graph = graph
        self.p = p
        self.q = q
        self.num_walk_list = num_walk_list
        self.walk_length = walk_length

    def node2vec_walk(self, start_node):
        walk = [start_node]
        while len(walk) < self.walk_length:
            cur = walk[-1]
            cur_nbrs = list(self.graph.neighbors(cur))
            if len(cur_nbrs) > 0:
                if len(walk) == 1:
                    walk.append(np.random.choice(cur_nbrs))
                else:
                    prev = walk[-2]
                    probs = []
                    for nbr in cur_nbrs:
                        if nbr == prev:
                            probs.append(1 / self.p)
                        elif self.graph.has_edge(prev, nbr):
                            probs.append(1)
                        else:
                            probs.append(1 / self.q)
                    probs = np.array(probs)
                    probs = probs / probs.sum()
                    walk.append(np.random.choice(cur_nbrs, p=probs))
            else:
                break
        return walk

    def generate_walk_list(self):
        walk_list = []
        node_list = list(self.graph.nodes())
        for _ in range(self.num_walk_list):
            np.random.shuffle(node_list)
            for node in node_list:
                walk_list.append(self.node2vec_walk(node))
        return walk_list


# グラフの作成
G = nx.karate_club_graph()

# Node2Vecのパラメータ設定
p = 1
q = 1
num_walks = 10
walk_length = 5

# Node2Vecのインスタンス生成とウォークの生成
node2vec = Node2Vec(G, p, q, num_walks, walk_length)
walks = node2vec.generate_walk_list()

# Skip-gramモデルでの学習
model = Word2Vec(walks, vector_size=64, window=5, min_count=0, sg=1)

# ノードの埋め込みを表示
embedding_list = {node: model.wv[node] for node in G.nodes()}

# 最初のノードの結果だけ示す
pprint(embedding_list[0].round(4))

array([-0.0029,  0.0041,  0.0041,  0.0096, -0.005 , -0.0021,  0.0089,
        0.017 , -0.0034, -0.0142,  0.0112,  0.0022,  0.0132, -0.0026,
       -0.0064, -0.0133, -0.0026,  0.0073,  0.0091,  0.0139, -0.0057,
        0.0032,  0.0166, -0.0085, -0.004 ,  0.0147, -0.0019,  0.0005,
        0.0063, -0.0011,  0.0124,  0.0105, -0.021 , -0.0161,  0.0038,
        0.0123, -0.0114,  0.01  ,  0.0152,  0.0083,  0.0139, -0.0052,
       -0.0002,  0.0031, -0.0029, -0.0106, -0.0021, -0.0151, -0.01  ,
        0.0139,  0.0078,  0.0118,  0.012 ,  0.0159, -0.0003,  0.0037,
        0.0061, -0.0099,  0.0123, -0.0165,  0.0114,  0.002 , -0.0098,
        0.0085], dtype=float32)

応用例

メリット

スケーラビリティ：大規模なグラフに対しても効率的に計算が可能である。
フレキシビリティ：パラメータ $p$ と $q$ の調整により、探索の深さと幅をバランス良く調整できる。

デメリット

計算コスト：非常に大規模なグラフに対しては、計算コストが増加する可能性がある。
ハイパーパラメータの調整：適切なハイパーパラメータの選定が結果に大きく影響する。

結論

この記事では、古典ランダムウォーク、DeepWalk、Node2Vecの定義、性質、応用例について説明した。ランダムウォークを利用したグラフ埋め込み手法は、推薦システムやソーシャルネットワーク分析などにおいて有効であることが示された。具体的なPythonコードを通じて、実装の流れも理解できたのではないだろうか。

参考文献

Perozzi, A., Al-Rfou, R., & Skiena, S. (2014). DeepWalk: Online Learning of Social Representations. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ‘14).
Grover, A., & Leskovec, J. (2016). node2vec: Scalable Feature Learning for Networks. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ‘16).

[ランダムウォーク] 古典ランダムウォーク (DeepWalkとNode2Vec)

古典ランダムウォーク（DeepWalkとNode2Vec）

概要

ソースコード

github

google colaboratory

実行環境

古典ランダムウォークとは

定義

性質

DeepWalk

定義

アルゴリズム

Pythonによる実装例

Node2Vec

定義

アルゴリズム

Pythonによる実装例

応用例

推薦システムでの利用

メリット

デメリット

結論

参考文献

Related Articles