左のグラフ（34ノード・78エッジのKarate Clubネットワーク）を右のベクトル空間に変換すると、同じ派閥のノードが自然に集まる。グラフ上の「つながり」という離散的な情報が、機械学習で扱いやすい連続ベクトルに変換されている。この変換を学習するのがDeepWalkとnode2vecの目標だ。
SNSのユーザー数千万人を、たった128次元のベクトルに「翻訳」できたら何が嬉しいでしょうか。友達同士のユーザーは近いベクトルになり、コミュニティごとにベクトル空間上で固まり、「この人と趣味が近い人」を内積一発で探せるようになります。これがグラフ埋め込み（graph embedding）の世界です。グラフという、点と線でしか書けない離散的で扱いにくい対象を、機械学習が大好きな「連続なベクトル」へと変換する。その先駆けとなり、今なお実務で広く使われているのが DeepWalk と node2vec です。
これらの手法の核心にあるのは、一見すると不思議なアイデアです。「グラフの上をランダムに散歩して、訪れたノードの列を文章とみなし、自然言語処理の単語埋め込み手法（word2vec）をそのまま流用する」というものです。なぜ「散歩」が埋め込みを生むのか、なぜ「文章」のアナロジーが成り立つのか。本記事ではその理由を、ランダムウォークが定義する共起確率と、Skip-gram with negative sampling（SGNS）の目的関数から丁寧に導出します。
グラフ埋め込みは応用の宝庫です。推薦システムでは、ユーザー・商品の二部グラフから埋め込みを学び、内積でクリック率を予測します。異常検知・不正検知では、金融取引ネットワークから正常なノードの埋め込み分布を学び、そこから外れるノードを検知します。さらに生命情報学ではタンパク質間相互作用ネットワークから機能予測を、知識グラフではエンティティのリンク予測を行うなど、ノードをベクトル化できると一気に下流タスクの選択肢が広がります。
本記事の内容
- ランダムウォークがなぜ「グラフの文章」になるのか、その共起確率を定式化する
- Skip-gram with negative sampling の目的関数を導出し、word2vec との対応を明示する
- node2vec の return パラメータ $p$ と in-out パラメータ $q$ による2次マルコフ遷移を式で与える
- BFS的（構造同値）と DFS的（ホモフィリ）な埋め込みの違いを直感的に理解する
- Karate Club グラフで $p, q$ を変えてウォークを生成し、gensim で埋め込みを学習・可視化・分類する
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- グラフニューラルネットワーク（GNN）とは — グラフを扱う機械学習の全体像
- グラフ表現学習の基礎 — ノード・エッジをベクトル化する考え方
グラフは頂点集合 $V$ と辺集合 $E$ からなる $G = (V, E)$ で表されること、隣接行列 $\bm{A}$ の定義、確率分布とその対数尤度、ロジスティック回帰（シグモイド関数）の基礎を知っているとスムーズです。これらは本文中でも必要に応じて補足します。
グラフ埋め込みとは — なぜ「散歩」がベクトルを生むのか
まず、グラフ埋め込みが目指すゴールを直感的に押さえましょう。グラフ埋め込みとは、各ノード $u \in V$ に対して $d$ 次元の実ベクトル $\bm{z}_u \in \mathbb{R}^d$（典型的には $d = 128$）を割り当てる関数 $f: V \to \mathbb{R}^d$ を学習することです。このとき満たしてほしい性質は単純で、「グラフ上で近い・似ているノードは、ベクトル空間でも近くにある」というものです。
ここで自然な疑問が湧きます。「グラフ上で近い」とは何でしょうか。直接つながっている隣接ノードのことでしょうか。それとも数ホップ離れていても、同じコミュニティに属していれば近いとみなすべきでしょうか。この「近さ」の定義こそが、グラフ埋め込み手法の個性を決めます。DeepWalk と node2vec が採用した答えは、「ランダムウォークで頻繁に一緒に現れるノードどうしは近い」 というものです。
なぜランダムウォーク（ランダムな散歩）なのでしょうか。グラフ上のあるノードから出発し、隣接ノードへランダムに移動することを繰り返すと、移動しやすい（密につながった）領域に長く留まり、疎な領域は通り抜けにくくなります。つまりランダムウォークが生成するノードの列には、グラフの「つながりの濃淡」という構造情報が自然に染み込むのです。
ここで効いてくるのが自然言語処理とのアナロジーです。文章中で「機械」と「学習」が頻繁に隣り合うのは、それらの意味が関連しているからです。word2vec はこの共起の統計から単語の意味ベクトルを学びました。同じように、ランダムウォークが生成したノード列を「文章」、ノードを「単語」とみなせば、word2vec の機械をそっくり流用できます。これが DeepWalk の核心的なアイデアです。
ランダムウォークの長さやコーパスの量という量的な側面に加え、「どう散歩するか」という質的な側面を制御できれば、埋め込みに込める構造の種類まで操作できるはずです。これが node2vec の発想で、次節以降で順に組み立てていきます。
ランダムウォークが定義する共起確率
ランダムウォークを数式で定義しましょう。まず、最も素朴な 一様ランダムウォーク（DeepWalk が用いるもの）を考えます。現在ノード $v$ にいるとき、次のノード $x$ へ遷移する確率は、$v$ の隣接ノード $N(v)$ の中から一様に選ぶので
$$ \begin{equation} P(x \mid v) = \begin{cases} \dfrac{1}{\deg(v)} & (x, v) \in E \\[2mm] 0 & \text{otherwise} \end{cases} \end{equation} $$
です。$\deg(v) = |N(v)|$ はノード $v$ の次数（隣接ノード数）です。重み付きグラフの場合は、辺の重み $w_{vx}$ に比例させて $P(x \mid v) = w_{vx} / \sum_{y \in N(v)} w_{vy}$ とします。
このルールに従って、出発ノード $c_0 = u$ から長さ $\ell$ のノード列 $W_u = (c_0, c_1, c_2, \dots, c_{\ell})$ を生成します。$c_{i+1}$ は $c_i$ の隣接ノードから上式の確率で選ばれます。これを各ノードを出発点として $\gamma$ 回ずつ（$\gamma$ は walks per node と呼ぶ）繰り返すと、$|V| \cdot \gamma$ 本のウォークからなる「コーパス」が得られます。
次に、生成されたウォークから 共起 を抽出します。文章の word2vec と同じく、ウォーク中で中心ノード $c_i$ から前後 $w$ 個（ウィンドウ幅 $w$）以内に現れたノードを「文脈ノード」とみなします。すなわち、ペア集合
$$ \begin{equation} \mathcal{D} = \big\{ (c_i, c_j) \;\big|\; |i – j| \le w,\ i \ne j,\ (c_0, \dots, c_\ell) \in \text{Walks} \big\} \end{equation} $$
を考えます。$(c_i, c_j) \in \mathcal{D}$ は「中心ノード $c_i$ の文脈に $c_j$ が現れた」という1件の共起観測です。
ここで、ランダムウォークが定義する共起確率の意味を考えましょう。ノード $u$ から出発したウォークが、$t$ ステップ後にノード $v$ にいる確率は、遷移行列 $\bm{P}$（成分が $P(x \mid v)$）の $t$ 乗の $(u, v)$ 成分 $[\bm{P}^t]_{uv}$ で与えられます。したがって、ウィンドウ幅 $w$ の範囲でノード $u$ の文脈に $v$ が現れる期待回数は、おおよそ
$$ \begin{equation} \#(u, v) \ \propto\ \pi_u \sum_{t=1}^{w} \big( [\bm{P}^t]_{uv} + [\bm{P}^t]_{vu} \big) \end{equation} $$
に比例します。ここで $\pi_u$ はノード $u$ がウォークの中心として現れる頻度（一様ウォークなら定常分布 $\pi_u \propto \deg(u)$ に対応）です。この式が意味するのは、「$u$ から数ステップで到達しやすいノードほど、共起が多くなる」 ということです。密につながった領域内のノードどうしは $[\bm{P}^t]_{uv}$ が大きく、共起頻度が高くなります。これがランダムウォークに構造情報が染み込む仕組みの定量的な表現です。
赤と青の2本のウォーク軌跡を見ると、それぞれの出発点（ノード0とノード33）から密につながったコミュニティ内を優先的に移動しているのがわかる。矢印の向きに沿って移動しながら「文章」が生成され、その文章中で近くに現れたノードどうしが共起データとなる。ウォーク同士が重なる領域ほど、両コミュニティを橋渡しするブリッジノードである可能性が高い。
こうして得た共起データ $\mathcal{D}$ を「教師信号」として、各ノードのベクトルを学習します。その学習器が次節の Skip-gram です。
Skip-gramの目的関数 — 共起をベクトルに変換する
Skip-gram の発想は明快です。「中心ノード $u$ のベクトル $\bm{z}_u$ から、その文脈に現れるノード $v$ を予測できるようにベクトルを調整する」というものです。予測がうまくいくということは、文脈を共有するノードどうしのベクトルが似てくることを意味します。
予測を確率モデルで書きましょう。中心ノード $u$ が与えられたとき、文脈ノード $v$ が現れる条件付き確率を、softmax で
$$ \begin{equation} P(v \mid u) = \frac{\exp(\bm{z}_v’^\top \bm{z}_u)}{\sum_{x \in V} \exp(\bm{z}_x’^\top \bm{z}_u)} \end{equation} $$
とモデル化します。ここで重要なのは、各ノードが 2種類のベクトル を持つ点です。$\bm{z}_u$ は $u$ が中心のときの「入力ベクトル」、$\bm{z}_v’$ は $v$ が文脈のときの「出力ベクトル」です。これは word2vec の入力埋め込み行列 $\bm{W}_{\text{in}}$ と出力埋め込み行列 $\bm{W}_{\text{out}}$ にそのまま対応します。最終的にノード埋め込みとして使うのは通常 $\bm{z}_u$ の方です。
Skip-gram は、共起データ $\mathcal{D}$ の対数尤度を最大化します。
$$ \begin{equation} \mathcal{L} = \sum_{(u, v) \in \mathcal{D}} \log P(v \mid u) = \sum_{(u, v) \in \mathcal{D}} \left[ \bm{z}_v’^\top \bm{z}_u – \log \sum_{x \in V} \exp(\bm{z}_x’^\top \bm{z}_u) \right] \end{equation} $$
ウォーク列（ノード2, 1, 0, 7, 3）の中で、オレンジ色の中心ノード0から前後2個以内のノード（ノード2, 1, 7, 3）が「文脈ノード」となる。Skip-gramはこの矢印の方向にベクトルの内積が大きくなるように埋め込みを調整する。こうして「ウォークで近くに現れるノードは似たベクトルを持つ」という性質が自動的に学習される。
ところが、この式には深刻な計算量の問題があります。softmax の分母（正規化項）は、全ノード $x \in V$ にわたる和を含みます。$|V|$ が数百万になる大規模グラフでは、共起ペア1件ごとに数百万回の内積と指数計算が必要になり、現実的に学習できません。この障壁を取り除くのが、次節の負例サンプリングです。
負例サンプリング — softmaxの呪いを解く
softmax の分母を真面目に計算する代わりに、問題そのものを巧妙に置き換えます。「中心 $u$ から文脈 $v$ を当てる多クラス分類」を、「ペア $(u, v)$ は本物の共起か、それともデタラメに作ったニセモノか」を見分ける2値分類 にすり替えるのです。これが negative sampling（負例サンプリング）の核心です。
本物のペア（正例）はデータ $\mathcal{D}$ から取ります。ニセモノのペア（負例）は、文脈ノードをノイズ分布 $P_n(x)$ からランダムに引いて作ります。$(u, v)$ が「本物の共起である確率」を、シグモイド関数 $\sigma(z) = 1/(1 + e^{-z})$ を使って
$$ \begin{equation} P(\text{正例} \mid u, v) = \sigma(\bm{z}_v’^\top \bm{z}_u) = \frac{1}{1 + \exp(-\bm{z}_v’^\top \bm{z}_u)} \end{equation} $$
とモデル化します。内積 $\bm{z}_v’^\top \bm{z}_u$ が大きいほど、本物である確率が1に近づきます。
学習の目的は、正例には高い確率（1に近い）を、負例には低い確率（0に近い、すなわち $\sigma(-\cdot)$ が1に近い）を割り当てることです。1つの正例 $(u, v)$ に対して $k$ 個の負例 $v_1, \dots, v_k \sim P_n$ をサンプリングし、最大化すべき目的関数を次のように書きます。
$$ \begin{equation} \mathcal{L}_{\text{SGNS}} = \sum_{(u, v) \in \mathcal{D}} \left[ \log \sigma(\bm{z}_v’^\top \bm{z}_u) + \sum_{i=1}^{k} \mathbb{E}_{v_i \sim P_n} \log \sigma(-\bm{z}_{v_i}’^\top \bm{z}_u) \right] \end{equation} $$
第1項は正例 $(u, v)$ を正しく「本物」と判定させる項、第2項は $k$ 個の負例を正しく「ニセモノ」と判定させる項です。$\log \sigma(-z) = \log(1 – \sigma(z))$ なので、第2項は負例の内積を小さく（負に）押し下げる働きをします。
この目的関数の素晴らしい点は、全ノードの和が消えた ことです。各正例について計算するのは、$1$ 個の正例の内積と $k$ 個（典型的には $k = 5 \sim 20$）の負例の内積だけです。計算量が $|V|$ に依存しなくなり、大規模グラフでも学習可能になります。
ノイズ分布 $P_n(x)$ には、word2vec の慣習に倣って、ノードの出現頻度 $f(x)$ の $3/4$ 乗に比例する分布
$$ \begin{equation} P_n(x) = \frac{f(x)^{3/4}}{\sum_{y} f(y)^{3/4}} \end{equation} $$
がよく使われます。$3/4$ 乗は、頻度の高いノード（ハブ）を負例に選びすぎないよう、頻度差を緩やかに圧縮するためのヒューリスティックです。グラフでは $f(x)$ がノードの次数に概ね比例するため、次数の高いハブノードが負例として適度に選ばれるようになります。
上の緑のパネルが「実際のウォーク中で共起した正例ペア」で、シグモイド出力を1に近づけるよう学習する。下の赤のパネルが「ノイズ分布からランダムに作った負例ペア」で、シグモイド出力を0に近づける。全ノードにわたるsoftmaxの和を計算する代わりに、この「本物か偽物か」の2値判定に問題を置き換えることで、$|V|$に依存しない計算量で学習できるようになる。
なお、Levy と Goldberg（2014）は、SGNS の最適解が点ごとの相互情報量（PMI）行列の暗黙的な行列分解に対応することを示しました。すなわち、最適なベクトルは
$$ \begin{equation} \bm{z}_v’^\top \bm{z}_u = \log \frac{\#(u, v) \cdot |\mathcal{D}|}{\#(u) \cdot \#(v)} – \log k = \mathrm{PMI}(u, v) – \log k \end{equation} $$
を満たします。これは、Skip-gram が「共起の偏り（PMI）を内積で再現するように埋め込みを学ぶ」という、ランダムウォーク共起確率の節で見た直感を裏付ける美しい結果です。
ここまでで DeepWalk の全パーツ（一様ウォーク → 共起抽出 → SGNS）が揃いました。残る問いは「散歩の仕方をもっと賢く制御できないか」です。それが node2vec の貢献です。
node2vec — p/qで散歩を操る2次バイアスウォーク
DeepWalk の一様ランダムウォークには、探索戦略を選べないという制約があります。グラフを探索する古典的な戦略には2つの極端があります。出発点の近傍をくまなく調べる 幅優先探索（BFS） と、出発点からどんどん遠くへ進む 深さ優先探索（DFS） です。node2vec のアイデアは、ランダムウォークをこの BFS と DFS の間で連続的に調整できるようにすることです。
そのために node2vec は 2次（second-order）のバイアス付きウォーク を使います。一様ウォークが「現在ノードだけ」を見て次を決める1次マルコフ過程なのに対し、node2vec は「1つ前にいたノード」も覚えておき、次の遷移を決めます。直前ノードを $t$、現在ノードを $v$ とし、次の候補ノードを $x$ とすると、遷移確率は次の 探索バイアス $\alpha_{pq}(t, x)$ に比例します。
$$ \begin{equation} \alpha_{pq}(t, x) = \begin{cases} \dfrac{1}{p} & d_{tx} = 0 \\[2mm] 1 & d_{tx} = 1 \\[2mm] \dfrac{1}{q} & d_{tx} = 2 \end{cases} \end{equation} $$
ここで $d_{tx}$ は直前ノード $t$ と候補ノード $x$ の最短距離（ホップ数）で、ウォークが2次マルコフであることから $d_{tx} \in \{0, 1, 2\}$ の3通りしか取りません。各ケースの意味を順に見ましょう。
- $d_{tx} = 0$：$x = t$、すなわち今来た道を引き返す（1つ前のノードに戻る）。重みは $1/p$。
- $d_{tx} = 1$：$x$ が $t$ とも隣接している。これは $t, v, x$ が三角形をなす、いわば「足踏み」的な近傍探索。重みは $1$。
- $d_{tx} = 2$：$x$ が $t$ から2ホップ離れている。これは $t$ から見て新天地へ進む遠方探索。重みは $1/q$。
未正規化の遷移重みは、この探索バイアスと辺の重みの積 $\pi_{vx} = \alpha_{pq}(t, x) \cdot w_{vx}$ で、実際の遷移確率は
$$ \begin{equation} P(x \mid v, t) = \frac{\alpha_{pq}(t, x)\, w_{vx}}{\sum_{y \in N(v)} \alpha_{pq}(t, y)\, w_{vy}} \end{equation} $$
と正規化して得ます。重み無しグラフなら $w_{vx} = 1$ です。
return パラメータ $p$ の役割
$p$ は return parameter（リターンパラメータ）です。$d_{tx} = 0$ のケース、つまり直前のノードに引き返す確率の重みを $1/p$ で制御します。$p$ を小さく（例えば $p < 1$）すると $1/p$ が大きくなり、引き返しやすくなります。これは現在ノードの周辺を行ったり来たりして、局所的な近傍を密に探索 する効果を生みます。逆に $p$ を大きくすると引き返しにくくなり、すでに訪れたノードへの冗長な再訪を避けて、新しい領域へ進みます。
in-out パラメータ $q$ の役割
$q$ は in-out parameter（インアウトパラメータ）です。$d_{tx} = 2$ のケース、つまり出発点 $t$ から遠ざかる方向への遷移の重みを $1/q$ で制御します。$q < 1$ にすると $1/q$ が大きくなり、遠方ノードへ進みやすくなります。これはウォークが出発点からどんどん離れていく DFS的（深さ優先的）な探索 を促します。逆に $q > 1$ にすると遠方への遷移が抑制され、ウォークは出発点の近傍をぐるぐる回る BFS的（幅優先的）な探索 になります。
BFS的（構造同値）とDFS的（ホモフィリ）の違い
ここが node2vec の最も美しい洞察です。$p, q$ の設定で2種類の質的に異なる埋め込みが得られます。
$q > 1$（BFS的）→ 構造同値（structural equivalence）を捉える。 ウォークが出発点近傍を狭く探索すると、ノードの「局所的な役割」が埋め込みに反映されます。例えば「ハブ（中心的）」「ブリッジ（橋渡し）」「葉（末端）」といった構造的な役割が同じノードどうしは、たとえグラフ上で遠く離れていても似たベクトルになります。BFS的ウォークは各ノードの直近の近傍構造を繰り返し観測するため、近傍の「形」が似たノードを似たものとみなすのです。
$q < 1$（DFS的）→ ホモフィリ（homophily）を捉える。 ウォークが遠方まで足を延ばすと、同じコミュニティ（密につながった集団）に属するノードどうしが頻繁に共起します。その結果、「同じクラスタに属する」という意味で似たノードが近いベクトルになります。これは「類は友を呼ぶ」というホモフィリ仮説に対応し、コミュニティ検出やラベル伝播に向いた埋め込みです。
直感的に言えば、BFS的ウォークは「あなたが誰と似た役回りか」を、DFS的ウォークは「あなたがどの仲間集団に属するか」を見ています。下流タスクが役割推定（例：ネットワーク内の機能分類）ならBFS的に、コミュニティ分類ならDFS的に設定するのが定石です。なお $p = q = 1$ とおくと探索バイアスが全て1になり、node2vec は DeepWalk の一様ウォークに帰着します。すなわち DeepWalk は node2vec の特殊ケース です。
3つのパネルそれぞれで、t（直前ノード）→v（現在ノード）から次の候補ノードへの遷移確率が数値で示されている。左の一様ウォーク（DeepWalk）では全候補が等確率だが、中央のBFS的設定（q=4）では遠方への確率が大幅に低下する。右のDFS的設定（q=0.25）では遠方への確率が高まり、ウォークがどんどん遠くへ進んでいく様子がわかる。このp/qの調整が埋め込みに「役割」か「所属」かを選択的に込める鍵となっている。
理屈が揃ったので、実際に Karate Club グラフで $p, q$ を動かし、埋め込みがどう変わるかを目で見てみましょう。
Pythonでの実装
ここからは、有名な Zachary’s Karate Club グラフを題材に実装します。これは空手クラブ34人の交友関係を表すグラフで、内部対立により2つの派閥に分裂した実話に基づきます。各ノードには分裂後にどちらの派閥（コミュニティ）に属したかのラベルが付いており、コミュニティ分離の良いテストベッドになります。
まず、グラフを読み込んで構造を確認します。
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
np.random.seed(42)
# Karate Club グラフを読み込む
G = nx.karate_club_graph()
# 各ノードの派閥ラベル（'Mr. Hi' / 'Officer'）を 0/1 に変換
labels = np.array([0 if G.nodes[i]['club'] == 'Mr. Hi' else 1
for i in G.nodes()])
print(f"ノード数: {G.number_of_nodes()}")
print(f"エッジ数: {G.number_of_edges()}")
print(f"平均次数: {2 * G.number_of_edges() / G.number_of_nodes():.2f}")
print(f"派閥0の人数: {(labels == 0).sum()}, 派閥1の人数: {(labels == 1).sum()}")
# グラフを描画
plt.figure(figsize=(8, 6))
pos = nx.spring_layout(G, seed=42)
nx.draw_networkx_nodes(G, pos, node_color=labels, cmap='coolwarm', node_size=300)
nx.draw_networkx_edges(G, pos, alpha=0.3)
nx.draw_networkx_labels(G, pos, font_size=8)
plt.title("Zachary's Karate Club (color = faction)")
plt.axis('off')
plt.tight_layout()
plt.savefig('karate_graph.png', dpi=150, bbox_inches='tight')
plt.show()
この出力から、Karate Club が34ノード・78エッジの小さなグラフであること、2つの派閥がほぼ同人数（17人ずつ程度）に分かれていることが読み取れます。描画図を見ると、ノード0（Mr. Hi）とノード33（Officer）という2人のハブを中心に、青系と赤系の2クラスタが緩やかに分かれている様子が見えます。グラフ埋め込みの目標は、この空間的な分離をベクトル空間でも再現することです。
2次バイアスウォークの実装
node2vec の心臓部である、$p, q$ 付き2次ランダムウォークをスクラッチで実装します。直前ノード prev と現在ノード cur の両方を引数に取り、探索バイアスで重み付けして次ノードを選ぶ点がポイントです。
def node2vec_step(G, prev, cur, p, q):
"""直前ノード prev, 現在ノード cur から次のノードを1ステップ選ぶ"""
neighbors = list(G.neighbors(cur))
if len(neighbors) == 0:
return cur
weights = []
prev_neighbors = set(G.neighbors(prev)) if prev is not None else set()
for x in neighbors:
if prev is None:
alpha = 1.0 # ウォーク開始直後はバイアスなし
elif x == prev:
alpha = 1.0 / p # d_tx = 0: 引き返す
elif x in prev_neighbors:
alpha = 1.0 # d_tx = 1: 三角形（共通隣接）
else:
alpha = 1.0 / q # d_tx = 2: 遠方へ進む
weights.append(alpha)
weights = np.array(weights)
weights /= weights.sum() # 確率に正規化
return np.random.choice(neighbors, p=weights)
このコードは前節で導出した遷移確率 $P(x \mid v, t) \propto \alpha_{pq}(t, x)$ をそのまま実装したものです。x == prev が $d_{tx}=0$、x in prev_neighbors が $d_{tx}=1$（直前ノードの隣接でもある＝三角形を形成）、それ以外が $d_{tx}=2$ に対応します。重みを正規化して np.random.choice で次ノードをサンプリングしている点も、定義式に忠実です。
次に、このステップ関数を使って長さ $\ell$ のウォークを各ノードから $\gamma$ 本ずつ生成し、コーパスを作ります。
def generate_walks(G, p, q, num_walks=10, walk_length=80):
"""各ノードを起点に num_walks 本、長さ walk_length のウォークを生成"""
walks = []
nodes = list(G.nodes())
for _ in range(num_walks):
np.random.shuffle(nodes) # 起点順をシャッフル
for start in nodes:
walk = [start]
prev = None
cur = start
for _ in range(walk_length - 1):
nxt = node2vec_step(G, prev, cur, p, q)
walk.append(nxt)
prev, cur = cur, nxt
# gensim は文字列トークンを期待するので str に変換
walks.append([str(n) for n in walk])
return walks
左のBFS的ウォーク（q=4）では、出発点（金の星ノード0）の近傍を密に探索し、訪問ユニークノード数が少なく同じ近傍をぐるぐると巡回する。右のDFS的ウォーク（q=0.25）では、同じ出発点からグラフ全体に広く足を延ばし、異なるクラスタのノードまで到達している。この軌跡の違いが、学習後の埋め込みに「局所的な役割」か「所属コミュニティ」かを埋め込む差となる。
num_walks（walks per node $\gamma$）と walk_length（ウォーク長 $\ell$）が、コーパスの量を決めるハイパーパラメータです。ここでは各ノードから10本、長さ80のウォークを生成します。34ノードなので合計340本、各80ノードのコーパスができます。prev, cur = cur, nxt で1ステップずつ状態を更新している点が、2次マルコフ過程を実現する肝です。
gensimでSkip-gramを学習する
生成したウォークコーパスに対し、gensim の Word2Vec を Skip-gram + 負例サンプリングモードで適用します。これが SGNS の目的関数を最適化する部分です。
from gensim.models import Word2Vec
def learn_embeddings(walks, dim=16, window=5, epochs=100):
"""ウォークコーパスから Skip-gram(負例サンプリング) で埋め込みを学習"""
model = Word2Vec(
sentences=walks,
vector_size=dim, # 埋め込み次元 d
window=window, # ウィンドウ幅 w
sg=1, # sg=1: Skip-gram（sg=0 は CBOW）
negative=5, # 負例サンプリング数 k
min_count=0, # 全ノードを語彙に含める
epochs=epochs,
workers=1,
seed=42,
)
# ノード順に埋め込みベクトルを並べた行列を返す
emb = np.array([model.wv[str(i)] for i in range(len(G.nodes()))])
return emb
sg=1 で Skip-gram、negative=5 で1正例あたり $k=5$ 個の負例サンプリングを指定しています。window=5 がウィンドウ幅 $w$、vector_size=16 が埋め込み次元 $d$ です。Karate Club は小さいので $d=16$ で十分ですが、大規模グラフでは128程度が標準です。min_count=0 は出現回数の少ないノードも語彙から除外しないための設定で、グラフ埋め込みでは全ノードを残す必要があるため必須です。
p/qを変えて埋め込みを可視化する
いよいよ本題です。DeepWalk相当（$p=q=1$）、BFS的（$q$ 大）、DFS的（$q$ 小）の3条件で埋め込みを学習し、2次元に射影して比較します。可視化には主成分分析（PCA）で16次元を2次元へ落とします。
from sklearn.decomposition import PCA
# 3つの設定: (p, q, ラベル)
settings = [
(1.0, 1.0, "DeepWalk (p=q=1)"),
(1.0, 4.0, "BFS-like (q=4, structural)"),
(1.0, 0.25, "DFS-like (q=0.25, homophily)"),
]
embeddings = {}
fig, axes = plt.subplots(1, 3, figsize=(16, 5))
for ax, (p, q, name) in zip(axes, settings):
walks = generate_walks(G, p=p, q=q, num_walks=10, walk_length=80)
emb = learn_embeddings(walks, dim=16, window=5, epochs=100)
embeddings[name] = emb
# 16次元 → 2次元 へPCAで射影
emb_2d = PCA(n_components=2).fit_transform(emb)
ax.scatter(emb_2d[:, 0], emb_2d[:, 1], c=labels, cmap='coolwarm', s=120)
for i in range(len(labels)):
ax.annotate(str(i), (emb_2d[i, 0], emb_2d[i, 1]), fontsize=7)
ax.set_title(name)
ax.set_xlabel('PC1'); ax.set_ylabel('PC2')
ax.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('node2vec_embeddings.png', dpi=150, bbox_inches='tight')
plt.show()
3枚の散布図を見比べると、いずれの設定でも色（派閥ラベル）ごとにノードが概ね左右や上下に分離していることが読み取れます。特に DFS的（$q=0.25$）の設定では、同じ派閥のノードが密に固まり、2つのクラスタの間に明確な隙間ができやすくなります。これはホモフィリ、すなわち「同じコミュニティに属するノードを近づける」効果が強く出ているためです。一方 BFS的（$q=4$）では、派閥の境界付近にいるノードや、両派閥に橋渡しするノードの配置が DFS的とは異なる傾向を示します。$p=q=1$ の DeepWalk はその中間的な分離を見せます。コミュニティ分離だけが目的なら DFS的設定が有利だと、この図から直感的に納得できます。
ロジスティック回帰でノード分類精度を比較する
「目で見て分離している」だけでは定量評価になりません。学習した埋め込みを特徴量に使い、派閥ラベルをロジスティック回帰で予測する分類精度で、3設定を客観的に比較します。
from sklearn.linear_model import LogisticRegression
from sklearn.model_selection import cross_val_score
print("=== ノード分類精度（5-fold CV accuracy）===")
for name, emb in embeddings.items():
clf = LogisticRegression(max_iter=1000)
# ノード埋め込みを特徴量、派閥を正解ラベルとして交差検証
scores = cross_val_score(clf, emb, labels, cv=5)
print(f"{name:35s}: {scores.mean():.3f} ± {scores.std():.3f}")
実行すると、典型的には次のような結果が得られます（乱数や環境で多少前後します）。
=== ノード分類精度（5-fold CV accuracy）===
DeepWalk (p=q=1) : 0.886 ± 0.093
BFS-like (q=4, structural) : 0.857 ± 0.121
DFS-like (q=0.25, homophily) : 0.914 ± 0.083
この数値から、コミュニティ（派閥）分類という今回のタスクでは、ホモフィリを捉える DFS的設定（$q=0.25$）が最も高い精度を出すことが確認できます。これは可視化で見たクラスタ分離の良さと整合しています。BFS的設定がやや劣るのは、このタスクが「ノードの構造的役割」ではなく「所属コミュニティ」を当てる問題だからです。タスクの性質に応じて $p, q$ を選ぶことの重要性が、数値ではっきり示されました。
埋め込み次元と精度の関係
最後に、埋め込み次元 $d$ を変えたときに分類精度がどう変化するかを確認し、次元の役割を体感します。
dims = [2, 4, 8, 16, 32, 64]
acc_by_dim = []
walks = generate_walks(G, p=1.0, q=0.25, num_walks=10, walk_length=80)
for d in dims:
emb = learn_embeddings(walks, dim=d, window=5, epochs=100)
clf = LogisticRegression(max_iter=1000)
acc = cross_val_score(clf, emb, labels, cv=5).mean()
acc_by_dim.append(acc)
plt.figure(figsize=(8, 5))
plt.plot(dims, acc_by_dim, 'o-', color='teal', linewidth=2)
plt.xscale('log', base=2)
plt.xlabel('Embedding dimension d')
plt.ylabel('5-fold CV accuracy')
plt.title('Node classification accuracy vs embedding dimension')
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('node2vec_dim.png', dpi=150, bbox_inches='tight')
plt.show()
このグラフから、埋め込み次元が極端に小さい（$d=2$）ときは精度がやや低く、$d=8 \sim 32$ あたりで精度が頭打ちになり、それ以上次元を増やしても大きな改善はないことが読み取れます。Karate Club は34ノードと小規模なため、少ない次元でも構造を十分表現できるのです。実務の大規模グラフでは、より高い次元（128程度）が必要になりますが、「ある程度以上は次元を増やしても効果が逓減する」という傾向は共通しています。次元はメモリ・計算コストとのトレードオフで決めるべきハイパーパラメータだと分かります。
DeepWalkからGNNへ — グラフ埋め込みの系譜
DeepWalk と node2vec は革新的でしたが、「新しいノードが追加されると再学習が必要」「ノードの属性（特徴量）を使えない」という本質的な制約を持ちます。この制約を乗り越えるため、次の世代の手法が生まれました。
word2vec（2013）からDeepWalk（2014）へ、さらにnode2vec（2016）とGraphSAGE（2017）の分岐点が手法の系譜として示されている。左のランダムウォーク系（DeepWalk/node2vec）はトランスダクティブで特徴量を必要としないため実装が簡単だが、新ノードへの汎化ができない。右のGNN系（GraphSAGE以降）はメッセージパッシングで特徴量を集約し、未知のノードにも一般化できる帰納的な学習を実現している。どちらが優れているというわけではなく、グラフに属性情報があるかどうかや、オンラインで新ノードを処理する必要があるかどうかで選択肢が変わる。
ランダムウォーク系は「グラフ構造だけを使って表現学習する」という純粋な問いへの答えとして、今でも特徴量の乏しいグラフ（Webリンク、交友ネットワーク等）での実装容易性から実務で重宝される。GNN系への橋渡し役として、そのアイデアの本質を理解することは依然として価値があります。
まとめ
本記事では、DeepWalk と node2vec によるグラフ埋め込みの理論と実装を解説しました。
- 基本アイデア：グラフ上のランダムウォークが生成するノード列を「文章」、ノードを「単語」とみなし、自然言語処理の word2vec を流用してノードをベクトル化する
- 共起確率：ランダムウォークの遷移行列 $\bm{P}$ の $t$ 乗が共起頻度を決め、$u$ から数ステップで到達しやすいノードほど共起が多くなる。これに構造情報が染み込む
- Skip-gram with negative sampling：softmax の全ノード和を「正例 vs 負例」の2値分類に置き換えることで、計算量を $|V|$ から切り離す。最適解は PMI 行列の暗黙的分解に対応する
- node2vec の $p, q$：直前ノードを記憶する2次マルコフウォークで、return パラメータ $p$ と in-out パラメータ $q$ により探索を BFS的（構造同値）と DFS的（ホモフィリ）の間で連続調整できる。$p=q=1$ で DeepWalk に帰着する
- 実験：Karate Club で $q$ を変えて埋め込みを学習し、コミュニティ分類では DFS的設定（$q<1$）が最も高い精度を出すことを確認した
ランダムウォークベースの埋め込みは、グラフの構造だけを使う「教師なし・トランスダクティブ」な手法です。新しいノードが追加されると再学習が必要で、ノードの特徴量（属性）を使えないという限界があります。これらを克服するのが、メッセージパッシングで特徴量を集約し、未知ノードにも一般化できるグラフニューラルネットワークです。
次のステップとして、以下の記事も参考にしてください。
- グラフニューラルネットワーク（GNN）とは — メッセージパッシングによる帰納的なグラフ学習
- グラフ表現学習の基礎 — ノード・エッジ・グラフ全体の埋め込み手法の俯瞰
参考文献
- B. Perozzi, R. Al-Rfou, S. Skiena, “DeepWalk: Online Learning of Social Representations,” KDD 2014.
- A. Grover, J. Leskovec, “node2vec: Scalable Feature Learning for Networks,” KDD 2016.
- T. Mikolov et al., “Distributed Representations of Words and Phrases and their Compositionality,” NeurIPS 2013.
- O. Levy, Y. Goldberg, “Neural Word Embedding as Implicit Matrix Factorization,” NeurIPS 2014.
