【前半】Pytorch Geometric で グラフのノード埋め込みを実装
本記事について
最近グラフ構造データの学習をしているので、備忘として学んだ内容や試したものをメモしておく。今回は「ノード埋め込み（node embeddings）」の内容をまとめる。なお学習にあたって、スタンフォード大学の講義：CS224W: Machine Learning with Graphsを教材として使用しており、ここに書く内容もこの講義資料を一部引用している。
グラフデータとは
グラフデータとは、「ノード」とノード同士のつながりの情報を表す「エッジ」で表現されるデータである。この世に存在する様々なものや事象が、グラフデータの形式で表現することができる。以下にいくつか例を出す。
| ノード | エッジ | |
|---|---|---|
| 食物網 | 動植物の種 | 食べる / 食べられるの関係 |
| 論文のネットワーク | 論文 | 引用する / 引用されるの関係 |
| ソーシャルネットワーク | 人物 | 交友関係 |
| 分子構造 | 原子 | 原子間の化学結合 |
グラフデータと機械学習
前述のとおりグラフ構造で表現されるものや事象は数多く存在し、人間にとって身近な現象もグラフデータとして記述できることから、グラフデータの解析技術は重要視されてきた。特に近年は機械学習の技術の発展に伴い、グラフデータに対して機械学習を応用する研究が盛んに行われている。
CS224W 1. Introduction; Machine Learning for Graphsから引用
ノード埋め込みとは
グラフデータに対し機械学習等のデータ解析技術を用いて何らかのタスクを解く場合、グラフのトポロジーやノード間の関係性といった「ネットワーク構造の情報」を解析可能な形式（数値データ）に加工してやる必要がある。ノード埋め込み（node embeddings）は、各ノードをベクトル表現にエンコードすることで、ネットワーク構造の情報を解析可能な形に変換するアプローチの一種である。
CS224W 3. Node Embeddingsから引用
グラフを構成する各ノードを、実数ベクトルとして表現することで、例えば以下のようなタスクの特徴量として活用することができる。
- ノードの属性の分類（Node Classification）
- グラフの属性の分類（Graph Classification）
- ノード間にエッジが存在するか否かの予測（Link Prediction）
また、機械学習タスク以外にも、埋め込み表現のベクトル同士の類似度を計算することで、そのノードに類似するノードを探し当てる、といったタスクに活用することも考えられる。
node2vec
今回は Pytorch Geometric (PyG) に実装されている node2vec という手法を用いて、ノード埋め込みの実装を確認してみる。2016年に発表された node2vec: Scalable Feature Learning for Networks という論文で提案された手法である。
手法の概要としては、
- あるノードを起点に、エッジをつたってランダムウォーク（※）する
- 1.を違うノードについて繰り返すことで、[ノードA, ノードB, ノードC,,,]のようなシーケンスデータを作る
- 2.で得られたシーケンスデータをもとに、skip-gramでノードの埋め込み表現を得る
というものである。
※本手法では完全にランダムにノード間を移動するのではなく、パラメータp, qを導入することで、近隣のノードの関係を重視して見に行くか、より遠くのノードの関係を重視して見に行くか、を制御することができる。これは、タスクに応じてどのような戦略でシーケンスをサンプリングするか？を変えることができることを意味する。あくまで自分の理解だが、これが本手法のエッセンスであり、旧手法の DeepWalk などとの差別化ポイントである。
手法の詳細な内容については、原論文を確認するか、以下の記事の説明を参照するのが良いと思う。
前半はここまで。
後半は実際に Pytorch Geometric を使って node2vec を試してみる。
Discussion