卒論のためにNode2Vecの論文を読んだので、この手法でネットワークの構造を学習する方法について解説します。数式を追わなくてもある程度理解できるようになっていると思います。

参考元

元論文: node2vec: Scalable Feature Learning for Networks
PyTorch GeometricのNode2Vecモデル: torch_geometric.nn.models.Node2Vec
再現実装の際にPyTorch Geometric(PyG)のモデルを用いたので、論文に明記されていない学習方法などはこちらを参考にしました。

Node2Vecとは

Node2Vecは、

ランダムウォークによってグラフの特徴が乗った系列を生成する
生成したウォークの系列をWord2VecのSkip-Gramモデルの入力とし、目的関数を最適化する

という手順でグラフの分散表現を得るモデルです。

2のSkip-Gramモデルについて本稿では深入りしませんが、ランダムウォークの系列をWord2Vecの単語列に見立てて同じことをやっていると考えると直観的に理解しやすいと思います。

独自のパラメータによってランダムウォークにバイアスをかけることで、近傍を重点的に探索してコミュニティ構造を埋め込んだり、構造的同値性(ハブなど役割の同一性)を検知したりできます。

半教師あり学習によって計算速度と精度を両立しており、ノードのラベル予測やノード同士のリンク予測などに使えるため、応用の幅が広いです。

ネットワークとは

ここでのネットワークとは、ノード(点)がエッジ(枝)で結ばれたものを指します。
エッジに重みがある重み付きグラフ、向きがある有向グラフなどいくつか分類がありますが、Node2Vecのアルゴリズムはいずれにも適用が可能です。

目的関数

数式を使わない要約

Node2Vec独自のアルゴリズムに従って、ネットワーク上をランダムウォークします。このとき、「実際に得られたランダムウォークのサンプルが発生する確率」が大きくなるように学習することで、サンプリングの結果に即したもっともらしい分散表現が得られます。

※ 分散表現とは、ノードごとの特徴をベクトル(数値の列)で表現したもの。
ランダムウォークの結果をもとに、表現$f$を最適なものにすることが目標。

ただし、真面目に最大化しようとすると計算量が膨大になるので、Negative Samplingという手法を用いて近似的に目的関数の最適化を達成します。

目的関数

ネットワーク: $G=(V,E)$
特徴空間への埋め込み: $f:V→\mathbb{R}^d$
サンプリングアルゴリズム: $S$
$S$によって生成されたネットワーク近傍: $N_S(u)\subset V (u\in V)$

得られたサンプルに対する対数尤度を最大化します。すなわち、最適化問題を
$$max_f\quad \sum_{u\in V}{\log{Pr(N_S(u)|f(u))}}$$

とし、問題を扱いやすくするために、以下の仮定を置きます。

各近傍ノードごとで尤度は独立である:
$$Pr(N_S(u)|f(u))=\prod_{n_i\in N_S(u)}Pr(n_i|f(u))$$
特徴空間では、注目するノード(ソースノード, source node)$u$とその近傍ノード(neighborhood node)$n_i$が相互に対称的な影響をもつ。また、以下の条件付き尤度を内積のソフトマックス関数で定義する:
$$Pr(n_i|f(u))=\frac{exp(f(n_i)・f(u))}{\sum_{v\in V}exp(f(v)・f(u))}$$

以上の仮定のもとで、目的関数は以下のように書けます。
$$
max_f\quad \sum_{u\in V} (-\log{Z_u}+\sum_{n_i\in N_S(u)}f(n_i)・f(u))
$$$$Z_u=\sum_{v\in V}exp(f(v)・f(u)): 分配関数$$

分配関数$Z_u$は全ノード$v\in V$に対して和をとっているため計算コストが高く、実際にはNegative Samplingを用いて近似的に目的関数の最大化を行います。

学習の流れ

Node2Vecの学習は、大まかに以下の流れで行われます。

ランダムウォークの生成
ネットワーク上の全てのノードを始点として、後述するアルゴリズムでランダムウォークを行います。ノードごとにとるサンプル数や、ウォークの長さはパラメータで指定します。
損失関数の計算
ランダムウォークの結果に基づいて損失関数を計算します。詳細な説明は省きますが、この損失関数を最小化する解が、もとの目的関数を最大化できる。損失関数の計算法については後述します。
分散表現の更新
確率的勾配降下法(SGD)により、分散表現を更新します。損失関数の勾配から、損失関数が小さくなる方向に学習します。

損失関数の計算方法

先述した目的関数の計算は時間的コストが高いので、Negative Samplingの考え方に基づいて簡略化した損失関数を考えます。

(Negative Samplingは、多クラス分類を2クラス分類に近似することで計算を簡略化する方法。そのうち解説記事を書く予定です。)

数式を使わない要約

ランダムウォークアルゴリズムで生成された系列には、ネットワークの特徴が乗っているはずです。例えば、多くのエッジで密接に繋がれたコミュニティがあれば、そのコミュニティのノードがまとまってウォークの系列に現れる確率は高いと考えられます。

そこで、ランダムウォークに現れたノード同士の内積(ここでは、類似度の指標)と、ランダムに生成された系列のノード同士の内積を考えます。前者が大きければ損失が小さく、後者が大きければ損失が大きくなるように損失関数が設計されています。

定義

各ノード$u\in V$ごとに損失を求め、合計したものを求める損失とします。
$(u, v_1, v_2,...,v_n)$をあるランダムウォークとします。これを正例(positive sample)といい、この系列に出現するノード同士は関連性が高いと考えられます。そこで、関連性の低いノードを集めた負例(negative sample)を、始点を$u$に固定して次のように生成します。
$$(u, w_1, w_2,...,w_n)$$
ただし、$w_1,w_2,...,w_n$は、全く無作為に選びます。
ここで、始点とその他の点の分散表現との内積の和

$$
正例: D_{pos} = \sum_{i=1}^n f(u)・f(v_i)
$$$$
負例: D_{neg} = \sum_{i=1}^n f(u)・f(w_i)
$$

に対して、ノード$u$に対応する損失を

$$
-\log{\sigma(D_{pos})} - \log{(1 - \sigma(D_{neg}))}
$$

と定めます。ただし、$\sigma(.)$はロジスティックシグモイド関数で、

$$
\sigma(x)=\frac{1}{1+\exp{(-x)}}
$$

と定義されます。この定義によって、ランダムウォークに現れたノード同士の埋め込みの類似度が高ければ損失が小さく、関係のないノード同士の埋め込みの類似度が高ければ損失が大きくなります。

グラフの探索手法

グラフのどのような特徴を知りたいか

ネットワーク上のノードの性質を柔軟に読み取るために、以下の2つの性質に興味があります。

ホモフィリー(Homophily)
類似のコミュニティに属するノードは特徴空間で近いベクトルに埋め込まれる性質のこと。広い範囲のノード同士の依存関係を知ることによって読み取れるため、DFS(深さ優先探索)的なランダムウォークが有効。
構造的同値性(Structural Equivalence)
構造的役割(多くのノードの中継となるハブなど)が類似するノードは特徴空間で近いベクトルに埋め込まれるという性質のこと。近隣との接続関係を知れば十分なことが多いため、BFS(幅優先探索)的なランダムウォークが有効。

ランダムウォーク・アルゴリズム

数式を使わない要約

2つのパラメータ$p,q$を導入し、確率の偏ったランダムウォークを行います。
始点の近くをうろつきやすくなるか、始点から遠くに行きやすくなるかを意図的に制御できるので、ホモフィリーや構造的同値性といったネットワークの性質がランダムウォークに乗りやすくなリマス。

$p$: Return parameter
$p$が小さいと、前時刻にいたノードにすぐに帰還する確率が大きくなり、ローカルに探索できます。大きいと、近くに留まりにくくなるため探索の冗長性が減ります。
$q$: In-out parameter
$q$が小さい($q<1$)と始点から遠くに行きやすくなり、遠くを探索しやすくなります。大きいと、遠くに行きにくくなります。

遷移確率の定義

$t\rightarrow v\rightarrow x$とノードを遷移することを考え、時刻$t-1$でノード$v$にいるとします。
このとき、$v$から$x$に遷移する確率を以下のように定義します。

$c_i$: ランダムウォークで$i$番目に訪れたノード
$w_{vx}$: $v$から$x$に向かうエッジ$(v,x)$の重み
$d_{tx}$: $t$と$x$がエッジ何本分離れているか

P(c_i=x|c_{i-1}=v)=
\begin{cases}
    \frac{\pi_{vx}}{Z}\quad if\quad (v,x)\in E \\
    0\quad otherwise
\end{cases}

\pi_{vx}=\alpha_{pq}(t,x)・w_{vx}

\alpha_{pq}(t,x)=
\begin{cases}
    \frac{1}{p}\quad if\quad d_{tx}=0 \\
    1\quad if\quad d_{tx}=1 \\
    \frac{1}{q}\quad if\quad d_{tx}=2
\end{cases}

参考: 遷移確率の図(元論文より)

元いたノード$t$に戻る確率に重み$\frac{1}{p}$が、$t$とエッジで繋がっていないノードに進む確率に重み$\frac{1}{q}$が掛けられます。従って、パラメータ$p,q$の調整によってランダムウォークの傾向を調整できます。

エッジの分散表現

ノードの分散表現をリンク予測に応用するためには、ノードの組み合わせの埋め込みも考えたいです。そこで論文では、エッジの分散表現として以下の候補が提供されています。
ただし、以下の表現はエッジの分散表現$g$の$i\in\lbrace 1,...,d'\rbrace$番目の要素の式とします。

注目するエッジ: $(u,v)\in E$
エッジの埋め込み: $g:V\times V\rightarrow \mathbb{R}^{d'}$

エッジ埋め込みの手法	第$i$要素
Average	$\frac{f_i(u)+f_i(v)}{2}$
Hadamard	$f_i(u)*f_i(v)$
Weighted-L1	$\|f_i(u)-f_i(v)\|$
Weighted-L2	$\|f_i(u)-f_i(v)\|^2$

おわりに

PyTorch Geometricを用いて簡単な再現実装をしたので、それも公開する予定です。

直観的な説明が多かったですが、詳しく理解したい人はNegative Samplingの論文やNCE(Noise Contrastive Estimation)などについて調べてみると良いと思います。