DeepWalkの概要とアルゴリズム及び実装例について

DeepWalkについて

DeepWalkは、Perozziらにより”DeepWalk: Online Learning of Social Representations“で報告されたグラフデータ解析のための機械学習アルゴリズムの一つであり、特に、ノードの表現学習（Node Embedding）と呼ばれるタスクに適したものとなる。これは、ノードを低次元のベクトル空間に埋め込むことを目的とした手法で、ノードがグラフ内で隣接するノードと共有する情報をキャプチャし、その情報を使用してノードの埋め込みを学習する。

DeepWalkの特徴は以下のようになる。

1. ランダムウォーク（Random Walks）: DeepWalkは、グラフ内のノードをランダムに選んでランダムウォークを実行する。ランダムウォークは、ノードを訪れる過程でノード間の関連性を捉える。具体的には、グラフ上でのランダムウォークを繰り返し行うことでノードの列を数多く生成し、その列を自然言語における単語列とみなしてエンべディングを行う。ランダムウォークの詳細は”ランダムウォークの概要とアルゴリズム及び実装例“を参照のこと。

2. スキップグラム（Skip-gram）: DeepWalkでは、ランダムウォークの過程で収集されたノードのシーケンスを使用して、スキップグラムモデルをトレーニングする。スキップグラムは、Word2Vecなどの自然言語処理のタスクなどで使用され単語列から各単語のエンべディングをつくる手法となる。DeepWalkではそれをグラフに適用し、与えられた中心ノードの周りのコンテキストノードを予測している。スキップグラムの詳細は”SkipGramの概要とアルゴリズム及び実装例“を参照のこと。

3. ノード埋め込み（Node Embedding）: スキップグラムモデルをトレーニングすることにより、各ノードは低次元のベクトルで表現される。これらのベクトルは、ノード間の類似性や関連性を捉えたものであり、後でクラスタリング、分類、推薦などのタスクに使用できる。DeepWalkにおける入力はグラフであり、出力は各ノードの潜在表現であるベクトルとなる。

DeepWalkは、グラフデータから意味的に豊かなノード埋め込みを学習するための効果的な手法として広く使用されており、さまざまな社会ネットワークにおける多ラベル分類問題において、訓練例が少ない場合でも高い性能を示している。また並列実装によって大規模グラフの表現学習を行うことも可能で、アルゴリズムのスケーラビリティもある。

“DeepWalk: Online Learning of Social Representations“での実験結果からも、BlogCatalog、Flikr、YouTubeなどのデータセットにおける多ラベリングにおいて　、ベースライン手法であるスペクトラルクラスタリング(Spectral Clustering)、エッジクラスタ(Edge Cluster)、モジュラリティ(Modularity)と比較して高精度であり、特にラベル付き頂点の数が少ない場合において優位であると報告されている。

さらに、DeepWalkの後継として、より高度なグラフ埋め込みアルゴリズムである”Node2Vecの概要とアルゴリズム及び実装例について“で述べているNode2Vecや”GraphSAGEの概要とアルゴリズム及び実装例について“で述べているGraphSAGEなどが開発されている。これらの手法は、さまざまなアプリケーションでグラフデータを解析し、ノードの特性や関係性を理解するのに役立てられている。

DeepWalkのアルゴリズムについて

DeepWalkの問題定義は以下の様になる。

与えられたグラフのノード集合を\(\mathbf{V}\)、エッジ集合を\(\mathbf{E}\)とし、各ノードがS種類の属性を持ち(\(\mathbf{X}\in\mathbb{R}^{|V|\times S}\))、ノードのラベル集合をyとし、全ノードのラベルをYとする(\(\mathbf{Y}\in\mathbb{R}^{|V|\times |y|}\))。部分的にラベルづけされたグラフは\(G_L=(\mathbf{V},\mathbf{E},\mathbf{X},\mathbf{Y})\)で表される。

DeepWalkの目標は、小さい潜在次元数dであるベクトル表現\(\mathbf{X}_E\in\mathbb{R}^{|V|\times d}\)を学習することとなる。ノード\(v_i\)からのランダムウォークを\(W_{v_i}\)、そのk番目のノードを\(W_{v_i}^{k}\)で表す。ランダムウォークを用いることの利点として以下がある。

• 局所的な探索は並列化可能となる
• 短いランダムウォークをもとに学習することで、グラフの一部が変更してもすべて計算し直す必要がない(変更した部分のランダムウォークを用いて学習モデルを構築できる)

DeepWalkでは、ランダムウォークによって得られた頂点の列や文を節とみなすことで言語モデリングの拡張を行っている。

言語モデルにおいては、語彙を\(\mathbf{V}\)、それに含まれる単語を\(\omega_i\in\mathbf{V}\)、単語列を\(\mathbf{W}_1^n=(\omega_0,\omega_1,\dots,\omega_n)\)としたとき、すべての訓練コーパスに対する\(Pr(\omega_n|\omega_0,\omega_1,.\dots,\omega_{n-1})\)を最大化することで、コーパスに現れる特定の単語列のもっともらしさを見積もっている。

これを拡張したDeepWalkでは、ノードの共起の確率分布だけではなく、潜在表現を学習することが目的となり、グラフの各ノードの潜在表現への関数として写像関数\(\Phi:v\in\mathbf{V}\rightarrow\mathbb{R}^{|V|\times d}\)を導入し、以下の式のもっともらしさを求めることが目的となる。

\[Pr(v_i|(\Phi(v_1),\Phi(v_2),\dots,\Phi(v_{i-1})))\]

ランダムウォークが長くなると、この条件付き確率の計算量が爆発するため、言語モデルの条件を緩和し、(コンテキストから1語を予測するのではなく)1語からコンテキストを予測する様にして、コンテキストは与えられた語の左右から構成されるものとする。さらに語順の制約をなくして、与えられた語\(v_i\)のコンテクストの任意の語の確率が高まる様なモデルにする。これにより以下の最適化問題が得られる。

\[\min_{\phi}-log Pr(\{v_{i-\omega},\dots,v_{i+\omega}\}\setminus v_i|\Phi(v_i))\]

すなわち\(\Phi(v_i)\)の分散表現から、\(v_i\)の周囲の語\(v_{i-\omega},\dots,v_{i+\omega}\)の確率を最大化する(先頭に負号がついているので全体として最小化する)問題となる。DeepWalkのアルゴリズムは、各ノードからランダムウォークを行い、言語モデルSkiGramを用いてノードの分散表現\(\Phi\)を更新していく処理を繰り返すものとなる。

SkipGramはウィンドウ内での単語の共起確率を最大化する言語モデルであり、以下の独立仮説により上記の条件付き確率を近似する。

\[Pr(\{v_{i-\omega},\dots,v_{i+\omega}\}\setminus v_i|\Phi(v_i))=\displaystyle\prod_{j=i-\omega,j\neq i}^{i+\omega}Pr(v_j|\Phi(v_i))\]

ここで、\(Pr(v_j|\Phi(v_i))\)の計算は計算量的に容易ではないので、階層的ソフトマックス(Hierarchical Softmax)を使って条件付き確率を分解する。階層的ソフトマックスは、多クラス分類に対して二分木を作り、2クラス分類の組み合わせで確率を計算する手法で、各ノードを二分木の葉に割り当て、\(Pr(v_j|\Phi(v_i))\)の予測問題を、二分木の階層構造の特定のパスの確率を最大化する問題とするものとなる。

ノード\(u_k\)からのパスが木のノード列\((b_0,b_1,\dots,b_{\lceil log|V|\rceil})\)の場合(\(b_0=root, b_{\lceil log|V|\rceil}=u_k\))、以下の様になる。

\[Pr(v_k|\Phi(v_j))=\displaystyle\prod_{l=1}^{\lceil log|V|\rceil}Pr(b_l|\Phi(v_j))\]

\(\mathbb{R}^d,Pr(b_l|\phi(v_j))\)はシグモイド関数によって以下の様にモデル化できる。

\[Pr(b_l|\Phi(v_j))=\frac{1}{1+e^{-\Phi(v_j)\cdot \Psi(b_l)}}\]

ここで\(\Psi(b_l)\in\mathbb{R}^d\)は木のノード\(b_l\)の親ノードに割り当てられた表現となる。これにより\( Pr(b_l|\Phi(v_j))\)の計算量をO(|V|)からO(log|V|)に減らすことができる。

DeepWalkのコードはPerozziのgitページにて公開されている。

DeepWalkの実装例について

DeepWalkの実装は、Pythonと一般的な機械学習ライブラリ（例: NumPy, scikit-learn）を使用して行うことができる。以下に、DeepWalkの基本的な実装例を示す。

1. ライブラリのインポート:

import networkx as nx # グラフ処理ライブラリ
import numpy as np
from gensim.models import Word2Vec # Word2Vecモデルのトレーニングに使用

2. グラフの読み込みまたは生成:

DeepWalkはグラフデータを入力として受け取る。以下は、NetworkXライブラリを使用して簡単な無向グラフを生成する例となる。

# 無向グラフの生成
G = nx.Graph()
G.add_edge(0, 1)
G.add_edge(0, 2)
G.add_edge(1, 2)
G.add_edge(1, 3)
# 他のノードとエッジを追加する

3. ランダムウォークの生成:

ランダムウォークを生成してシーケンスを収集する。以下はランダムウォークを生成する簡単な関数の例となる。

def generate_random_walks(graph, num_walks, walk_length):
    walks = []
    for _ in range(num_walks):
        for node in graph.nodes():
            walk = [node]
            for _ in range(walk_length - 1):
                neighbors = list(graph.neighbors(node))
                if len(neighbors) == 0:
                    break
                node = np.random.choice(neighbors)
                walk.append(node)
            walks.append(walk)
    return walks

4. スキップグラムモデルのトレーニング:

生成したランダムウォークシーケンスを使用してWord2Vecモデルをトレーニングする。Gensimライブラリなどが利用できる。

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

# Word2Vecモデルのトレーニング
model = Word2Vec(walks, vector_size=64, window=5, sg=1, workers=4)

# 学習したモデルを保存
model.save("deepwalk_model")

5. ノードの埋め込みの取得:

学習したWord2Vecモデルを使用して、各ノードの埋め込みを取得する。

# ノードの埋め込みを取得
node_embeddings = {str(node): model.wv[str(node)] for node in G.nodes()}

以上で、DeepWalkによって学習されたノード埋め込みが取得できまる。これをさまざまなグラフベースのタスクに使用することが可能となる。

DeepWalkの課題について

DeepWalkは優れたグラフ埋め込み手法ですが、いくつかの課題や制約も存在する。以下に、DeepWalkの主な課題について述べる。

1. グラフの局所性に対する敏感性:

DeepWalkはランダムウォークを使用してグラフを探索し、ランダムウォークの開始点に大きく依存する。したがって、グラフ内の局所的な構造に敏感であり、グラフ全体の大域的な情報を十分に捉えられない場合がある。これは、グラフが連結でない場合や、特定のノードからのランダムウォークがグラフ全体をうまくカバーできない場合に問題となる。

2. サンプリングバイアス:

DeepWalkはランダムウォークに基づいてノードのシーケンスを生成するが、これにより一部のノードが頻繁に訪れられ、他のノードが無視される場合がある。このサンプリングバイアスにより、ノードの埋め込みが不均衡になる可能性がある。

3. ハイパーパラメータの調整:

DeepWalkにはいくつかのハイパーパラメータ（例: ウィンドウサイズ、埋め込み次元数、ランダムウォークの数など）が存在し、これらのパラメータを適切に調整する必要がある。パラメータの選択が課題に大きな影響を与えるため、適切な調整が必要となる。

4. スケーラビリティの制約:

DeepWalkはランダムウォークを多数回実行し、Word2Vecモデルをトレーニングする必要がある。これにより、大規模なグラフに対して計算コストが高くなる可能性があり、スケーラビリティに制約がある場合、より効率的なアルゴリズムが必要となる。

5. 構造情報のみに依存:

DeepWalkはグラフの構造情報のみに依存して埋め込みを学習する。しかし、実際のアプリケーションでは、ノードの属性情報や時間情報などの他の情報も重要であることがある。DeepWalkはこれらの情報を考慮しないため、それらを活用するためには他の手法が必要となる。

DeepWalkの課題への対応策について

DeepWalkの課題への対応策として、以下のようなアプローチや改良が提案されている。

1. バイアスを削減する方法:

ランダムウォークにおいて、頻繁に訪れるノードと訪れにくいノードとのバイアスを削減する方法がある。例えば、ランダムウォークのスタート地点をランダムに選ぶ代わりに、ノードの重要度に基づいて選ぶことができる（例: “ページランクアルゴリズムの概要と実装“で述べているPageRankスコアに基づくランダムウォーク）。

2. 隣接情報の重みづけ:

ランダムウォークの際に、エッジ（ノード間の接続）をたどる際にエッジに重みをつけることで、重要なエッジを優先的に訪れるようにできる。これにより、エッジの重要性を考慮したランダムウォークが実現可能となる。

3. 高次元の埋め込み:

埋め込みの次元数を増やすことで、埋め込みの表現力を向上させることができる。しかし、高次元の埋め込みを扱う場合、計算コストが増加する可能性があるため、注意が必要となる。

4. 時間情報の組み込み:

グラフデータに時間情報がある場合、時間に基づいたランダムウォークを考慮することができる。時間情報を組み込むことで、時間に応じたノードの変化や関連性を捉えることが可能となる。

5. より高度なアルゴリズムの使用:

DeepWalkの後継として、より高度なグラフ埋め込みアルゴリズムが提案されている。例えば、”Node2Vecの概要とアルゴリズム及び実装例について“で述べているNode2Vecや”GraphSAGEの概要とアルゴリズム及び実装例について“で述べているGraphSAGE、”HARPの概要とアルゴリズム及び実装例について“で述べているHARPなどがあり、これらはDeepWalkの課題に対処するために設計されている。

6. 複数のビューの統合:

グラフに複数のビュー（構造情報、属性情報、時間情報など）がある場合、これらのビューを統合する手法を使用することができる。これにより、より豊かなノード埋め込みを学習することが可能となる。

7. グラフの前処理:

グラフの前処理やクリーニングを行うことで、不要なノードやエッジを削除し、ノイズを減少させることができる。これにより、埋め込みの品質が向上する可能性がある。”機械学習におけるノイズ除去とデータクレンジング、欠損値補間“も参照のこと。

参考情報と参考図書

グラフデータの詳細に関しては”グラフデータ処理アルゴリズムと機械学習/人工知能タスクへの応用“を参照のこと。また、ナレッジグラフに特化した詳細に関しては”知識情報処理技術“も参照のこと。さらに、深層学習全般に関しては”深層学習について“も参照のこと。

参考図書としては”グラフニューラルネットワーク ―PyTorchによる実装―“

“グラフ理論と機械学習“

“Hands-On Graph Neural Networks Using Python: Practical techniques and architectures for building powerful graph and deep learning apps with PyTorch“

“Graph Neural Networks: Foundations, Frontiers, and Applications“等がある。