本記事で使う記法

$\mathcal{G}$: グラフ
$v_i$: グラフ内の特定のノード
$\mathcal{V}$: グラフ内のノード集合
$\mathcal{N}(v^{(t)})$: ノード $v^{(t)}$ に隣接するノード集合
$\mathbf{u}_i$: ノード $v_i$ のベクトル表現（埋め込み）
$\mathbf{e}_i$: ノード $v_i$ のワンホットエンコーディングベクトル
$\mathbf{W}$: 学習対象の重み行列
$\mathcal{W}$: ランダムウォーク（ノード列）
$\mathcal{R}$: ランダムウォークの集合
$v_{\text{cen}}$ と $v_{\text{con}}$: 中心ノードと文脈ノード
$p(v_{con} | v_{cen})$: 中心ノード $v_{cen}$ の文脈で文脈ノード $v_{con}$ が観測される確率
$\sigma$: シグモイド関数

グラフ埋め込みについて

グラフ埋め込み（Graph Embedding）とは、グラフの各ノードを、その重要な情報を保持しながら低次元ベクトル表現に変換するプロセスです。このプロセスは一般にノード埋め込みとして知られており、主に以下の2つのドメインでノードを捉えます。

グラフドメイン：ノードはエッジの繋がり、つまり第2章で扱ったグラフ理論における「グラフ構造 $\mathcal{G}$ 内の $v_i$ 」として表現されます。
埋め込みドメイン：ノードは連続値を要素に持つベクトルによって表現されます。

グラフ埋め込みの目的は、グラフドメインの情報を埋め込みドメインで表現することにあります。つまり、グラフの構造や特性をベクトルとして表現し、その情報を失わないようにします。

グラフ埋め込みにおける重要な疑問

グラフ埋め込みをする際は以下の2点を考える必要があります：

どんな情報をベクトルに保存する必要があるのか？
どのようにしてその情報をベクトルに保持するのか？

これらの答えによって使用するグラフ埋め込みのアルゴリズムが異なってきます。保存する情報として、一般的に、ノードの近傍情報、ノードの構造的役割、ノードの状態、コミュニティ情報などが研究されています。

グラフ埋め込みのフレームワーク

グラフ埋め込みの一般的なプロセスは以下の4つの要素で構成されます。

マッピング関数 (Mapping)：グラフドメインから埋め込みドメインへのノードの写像を行います。
情報抽出器 (Extractor)：グラフから保存対象とする情報 $\mathcal{I} $ を抽出します。
再構成器 (Reconstructor)：埋め込みドメインの情報を使って、グラフ情報 $\mathcal{I}$ を再構成します。
目的関数 (Objective)：マッピング関数や再構成に関わるパラメータの学習のために、抽出された情報と再構成された情報を基に作成されます。

本章では、このフレームワークに沿って、グラフドメインの様々な情報を保持する代表的な手法を紹介します。

グラフ埋め込みのアルゴリズム

本記事では、単純グラフ（静的で無向なグラフ）に対するグラフ埋め込みアルゴリズムについて説明していきます。
グラフに埋め込む情報としては「ノードの共起性」、「構造的役割」、「ノードの状態」、「コミュニティの構造」などのバリエーションがあり、それらの保存対象の情報に応じたアルゴリズムが整備されています。
その中で、本記事では「ノードの共起性」と「ノードの状態」の埋め込みに絞って解説します。

DeepWalk：「ノード共起性」を保存する手法

まず、グラフ中のノード共起性を保存する方法であるDeepWalkについて解説します。焦点としては、グラフ中で共起する傾向のあるノードを特定し、それらの類似性を低次元ベクトル空間にマッピングする方法に関するものです。

プロセス1. マッピング関数の定義

マッピング関数 $f(v_i)$ は、グラフのノードを低次元ベクトル空間に変換するための重要な関数です。この関数の目的は、グラフ内の各ノード $v_i$ を対応する埋め込みベクトル $\mathbf{u}_i$ に写像することです。

具体的には、マッピング関数はルックアップテーブルを使用して実装されます。ルックアップテーブルとは、各ノードに割り当てられたインデックス $i$ を使って、そのノードの埋め込みベクトル $\mathbf{u}_i$ を取得する手法です。

マッピング関数の数学的表現は次のようになります：
$$
f(v_i) = \mathbf{u}_i = \mathbf{e}^T_i\mathbf{W}
$$
ここで、$\mathbf{e}_i$ はノード $v_i$ のワンホットエンコーディングを表し、$N$ はグラフのノードの総数 $|\mathcal{V}|$ を示します。ワンホットエンコーディングでは、ベクトル $\mathbf{e}_i$ の中でノード $v_i$ に対応する要素のみが 1 となり、他の要素はすべて 0 です。
また，$\mathbf{W}$ は $N \times d$ のサイズを持つ学習可能な重み行列であり、$d$ は埋め込みの次元数です。この行列の各行は、対応するノードの埋め込みベクトルを表します。

したがって、マッピング関数のパラメータの総数は $N \times d$ 個となり、これによりグラフの各ノードが低次元の埋め込みベクトルに変換されます。このプロセスにより、グラフ内のノードの関係や特性を、効率的に処理しやすいベクトル形式で表現することが可能になります。

プロセス2. ランダムウォークに基づく共起性の抽出の要約

DeepWalkは、ランダムウォークを用いてグラフ内のノード間の共起関係を抽出し、これを基にノードの埋め込みを学習する手法です。

グラフ上のランダムウォークの概念

グラフ上のランダムウォークは、グラフ $\mathcal{G}$ の任意のノード $v^{(0)}$ から始まり、隣接するノードを無作為に選択して移動するプロセスです。このプロセスは $T$ 個のノードを訪問するまで続けられ、その結果として得られるノードの列がランダムウォークとなります。

ランダムウォークの形式的定義

ランダムウォークでは、各ステップで次の移動先のノードを以下の確率で選択します：
$$
p(v^{(t+1)} | v^{(t)}) =
\begin{cases}
\dfrac{1}{d(v^{(t)})}, & v^{(t+1)} \in \mathcal{N}(v^{(t)}) \\\\
\phantom{11}0, & \text{otherwise}
\end{cases}
$$

ここで、$ d(v^{(t)})$ はノード $ v^{(t)} $ の次数、$\mathcal{N}(v^{(t)})$ は $v^{(t)}$ に隣接するノードの集合です。つまり、次の移動先は現在のノードの近傍から等確率でランダムに選ばれます。

ランダムウォークの生成

このランダムウォークを使ってグラフ全体の情報を捉えてみるためには、各ノードから $\gamma$ 個のランダムウォークを生成します。これにより、合計 $N \times \gamma$ 個のランダムウォークが得られます。このアルゴリズムでは、グラフ $\mathcal{G}$、ランダムウォークの長さ $T$、各ノードでのランダムウォーク生成回数 $\gamma$ を入力として与え、これらのランダムウォークの集合$\mathscr{R}$ を生成することになります。
具体的に、グラフ$\mathcal{G}$中の各ノード($v_0$)に対して、得られるランダムウォークは以下の通り：
$$
\mathcal{W} =\operatorname{RW}(\mathcal{G}, v^{(0)}, T)
$$

ランダムウォークに基づく共起性の抽出

生成したランダムウォークに基づいて共起性を抽出してみましょう。
例えば自然言語処理の分野では、単語「太陽」と単語「惑星」は同じ文章（センテンス）内で登場（共起）することが多いのでこれらの用語は共起性が高い単語同士といえるでしょう。

同じように生成されたランダムウォークは、グラフのノード集合 $\mathcal{V}$ を単語の集まりと見なす「人工言語」の文章として扱うことができます。このアプローチでは、グラフ上のノードの移動パターンを言語モデルにおける文章のように解釈し、ノード間の関係を言葉の共起関係として分析します。

実際の共起関係の抽出では、Skip-gramアルゴリズムが用いられます。
Skip-gramアルゴリズムは、言語モデルの一種で、文章中の単語間の共起関係を捉えることを目的としています。このアルゴリズムでは、ある中心単語 (center word) に対して、その周辺にある単語を文脈単語 (context word) として扱います。この文脈単語は、中心単語から一定の距離 $w$ 以内に位置する単語として定義されます。

このSkip-gramアルゴリズムの概念をランダムウォークに適用することで、グラフ内のノード間の共起関係を抽出することが可能になります。具体的には、ランダムウォーク内のノード間の関係を、中心ノード (center node)　$ v_{\text{cen}} $ と文脈ノード (context node) $ v_{\text{con}} $ のペアとして表現します。

共起関係を抽出するアルゴリズムでは、各ランダムウォーク $ \mathcal{W} $ に対して、その中のノード $ v^{(i)} $ ごとに、指定された範囲 $ j=1,\dots,w $ にわたってペア $ (v^{(i-j)}, v^{(i)}) $ と $ (v^{(i+j)}, v^{(i)}) $ を共起リスト$\mathcal{I}$に追加(append)していきます。このプロセスにより、ランダムウォーク中のノードの位置関係から共起情報が抽出され、グラフ内のノード間の関係性が明らかになります。

プロセス3. 共起性の再構成および目的関数の設計

共起性の再構成

共起性の再構成は、グラフ内のノード間の共起情報を埋め込みドメインで再現するプロセスです。このプロセスでは、グラフドメインで観測されるノード組の共起確率を、埋め込みドメインで再構成します。中心ノード $v_{cen}$ と文脈ノード $v_{con}$ のペアに対して、次のようなマッピング関数を用いて、各ノードの埋め込みを得ます：

$$
\begin{align}
f_{cen}(v_i) = u_i = e_i^T W_{cen}\\
f_{con}(v_i) = v_i = e_i^T W_{con}
\end{align}
$$

ここで、$f_{cen}$ と $f_{con}$ はそれぞれ中心ノードと文脈ノードのマッピング関数、$W_{cen}$ と $W_{con}$ は学習対象のパラメータです。

そして、中心ノード $v_{cen}$ の文脈で文脈ノード $v_{con}$ が観測される（共起）確率は、次のソフトマックス関数によってモデル化されます：

$$
p(v_{con} | v_{cen}) = \dfrac{\exp(f_{con}(v_{con})^T f_{cen}(v_{cen}))}{\displaystyle \sum_{v \in \mathcal{V}} \exp(f_{con}(v)^T f_{cen}(v_{cen}))}\tag{1}
$$

目的関数

上で定義した共起確率を用いると、共起リスト$\mathcal{I}$内のノード組の再構成確率は、以下のように定義されます：

$$\displaystyle
\mathcal{L}(W_{con}, W_{cen}) = \mathcal{I}' = \operatorname{Rec}(\mathcal{I}) = \prod_{(v_{con}, v_{cen}) \in \mathcal{I}} p(v_{con} | v_{cen})\tag{2}
$$

ここで、$\mathcal{I}'$ は再構成された共起リスト、$\operatorname{Rec}$ は再構成関数を表します。
直接的には式(2)が目的関数であり、この$\mathcal{I}'$を最大化（$\mathcal{L}$を最小化）するように、学習パラメータ$W_{cen}$と$W_{con}$を調整することでより良く共起性を保持したマッピング関数が得られることになります。

しかし、実際に式(1)で確率を計算することは、速度上の理由からとても困難を極めます。そこで、学習を高速化する「階層的ソフトマックス」や「ネガティブサンプリング」といった手法が採用されており、式(2)を改良した目的関数が通常設計されています。

node2vec：共起性を保存するその他の手法

node2vecは、グラフのノード間の共起関係を低次元のベクトル空間にマッピングするために、「偏りのあるランダムウォーク」（biased random walk）を採用します。これはDeepWalkの基本的なランダムウォークに比べて、ノードの近傍をより柔軟に探索することを可能にします。

偏りのあるランダムウォークの定義

node2vecでは、二次ランダムウォーク（second-order random walk）という特別なタイプのランダムウォークを使用します。このウォークは2つのパラメータ $p$ と $q$ に基づいています。ランダムウォークがノード $v^{(t-1)}$ から $v^{(t)}$ に移動した後、次のノード $v^{(t+1)}$ への（非正規化）移動確率は次のように定義されます：

$$
\alpha_{pq}(v^{(t+1)} | v^{(t-1)}, v^{(t)}) =
\begin{cases}
\dfrac{1}{p} & \text{if dis}(v^{(t-1)}, v^{(t+1)}) = 0\\
1 & \text{if dis}(v^{(t-1)}, v^{(t+1)}) =1\\
\dfrac{1}{q} & \text{if dis}(v^{(t-1)}, v^{(t+1)}) = 2
\end{cases}
$$

ここで、$\text{dis}(v^{(t-1)}, v^{(t+1)})$ はノード $v^{(t-1)}$ と $v^{(t+1)}$ の間の最短パスの長さです。

パラメータ $p$ と $q$ の意味

$p$: ノード $v^{(t-1)}$ から $v^{(t)}$ への移動直後にノード $v^{(t-1)}$ を再訪する確率を制御します。$p$ が小さいほどランダムウォークは再訪を促し、$p$ が大きいほど再訪する確率が低くなります。
$q$: 移動先のノードを「内側」と「外側」に区別します。$q > 1$ の場合は内側のノードに偏り、$q < 1$ の場合は外側のノードに偏った移動となります。

node2vecの応用

パラメータ $p$ と $q$ の制御により、異なる焦点を持つランダムウォークが生成されます。この確率分布に従ったランダムウォークを生成した後、node2vecの残りのステップはDeepWalkと同様です。これにより、グラフ内のノード間の共起関係を効果的に捉え、低次元のベクトル表現を生成します。

ノード状態の保存

第2章の「グラフ理論の基礎」で説明したようにノードが持つ中心性スコアのようなノードの大域的な状態は、グラフの重要な情報であると言えます。
そこで、ノードの共起性だけでなく、大域的な状態の保存するグラフ埋め込み手法が提案されています。共起性についてはDeepWalkと同じなので、ここでは大域的状態に関する情報の保存に注目して解説していくことにしましょう。

大域的な状態の保存

大域的な状態の保存では、ノードの中心性スコア（例：次数中心性、固有ベクトル中心性）などの大域的な状態スコアを直接保存するのではなく、そのランキング情報を保存することが目的となります。具体的には、情報抽出器がノードの大域的な状態スコアを計算し、それに基づいてノードをランク付けします。そして、再構成器がランキング情報を復元するように設計されています。

情報抽出

まずノードの大域的な状態スコアを計算し、次にノードを降順にランク付けします。
ノードの順位は $(v_{(1)}, \dots, v_{(N)})$ と表され、下付き添字は順位を示します。
このように情報抽出を行い、この情報を再構成するようにモデル化を行います。

再構成

再構成器は、ノード埋め込みを基に、抽出されたランキング情報を復元します。
大域的な状態スコアのランキングに関する確率は、ノード埋め込みベクトルを使って次のようにモデル化されます：

$$
p_{\text{global}} = \prod_{1\leq i<j\leq N}p(v_{(i)},v_{(j)}).
$$

ここで、$p(v_{(i)}, v_{(j)})$ はノード $v_{(i)}$ が $v_{(j)}$ より高い中心性スコアを持つ確率を表します。
この確率は次のようにモデル化されます：

$$
p\left(v_{(i)}, v_{(j)}\right) = \sigma\left(\mathbf{w}^{\top}(\mathbf{u}_{(i)} - \mathbf{u}_{(j)})\right),
$$

ここで $\mathbf{u}_{(i)}$ と $\mathbf{u}_{(j)}$ はそれぞれのノードの埋め込みであり、$\mathbf{w}$ は学習対象のパラメータベクトルです。

目的関数

目的関数 $\mathcal{L}_{\text{global}}$は以下のように定義されます：

$$
\mathcal{L}_{\text{global}} = -\log p_{\text{global}}.
$$

この目的関数は共起情報を保存する目的関数$\mathcal{L}$と組み合わせることで、学習した埋め込みが「共起情報」と「大域的な状態」の両方を保存できるようになります。

より詳細を知りたい方へ

以上、「グラフ深層学習」の第4章についてまとめました。
もし気に入っていただければ，ぜひ書籍版をご購入くださると嬉しいです．
本書の概要ページは以下になります．