🔦

【前半】Pytorch Geometric で グラフのノード埋め込みを実装

2022/09/08に公開約2,500字

本記事について

最近グラフ構造データの学習をしているので、備忘として学んだ内容や試したものをメモしておく。今回は「ノード埋め込み(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. あるノードを起点に、エッジをつたってランダムウォーク(※)する
  2. 1.を違うノードについて繰り返すことで、[ノードA, ノードB, ノードC,,,]のようなシーケンスデータを作る
  3. 2.で得られたシーケンスデータをもとに、skip-gramでノードの埋め込み表現を得る
    というものである。

※本手法では完全にランダムにノード間を移動するのではなく、パラメータp, qを導入することで、近隣のノードの関係を重視して見に行くか、より遠くのノードの関係を重視して見に行くか、を制御することができる。これは、タスクに応じてどのような戦略でシーケンスをサンプリングするか?を変えることができることを意味する。あくまで自分の理解だが、これが本手法のエッセンスであり、旧手法の DeepWalk などとの差別化ポイントである。

手法の詳細な内容については、原論文を確認するか、以下の記事の説明を参照するのが良いと思う。

https://recruit.gmo.jp/engineer/jisedai/blog/node2vec/

前半はここまで。
後半は実際に Pytorch Geometric を使って node2vec を試してみる。

Discussion

ログインするとコメントできます