Index
Graph Embedding
Graph Embedding とは、グラフの各ノードの構造情報を低次元のベクトルで表現する手法.
その際、グラフ上での近接性が保たれる必要がある.
すなわち、グラフ上で近いノード同士のベクトル表現も近くなければならない.
従来のグラフ表現における課題
- 高い計算コスト
- 低い並列度
- 機械学習手法の適用不可
これらの課題に対応するために、グラフ情報を低次元のベクトルで表現することがモチベーションになる.
次元圧縮
高次元データから低次元の表現を得る古典的な方法として、次元圧縮がある.
- 主成分分析 / PCA
- 多次元尺度構成法 / MDS
- 特異値分解 / SVD
- lsomap
これらはいずれも、高次元データから低次元データの表現を得る一般的な手法であるが、
多くのグラフ表現においては構造情報だけでなく、各ノードやエッジが情報を持っている場合もある.
それらの情報を含めての次元圧縮という意味では、これらの手法は十分とはいえない.
グラフ構造に着目した Embedding 手法
- DeepWalk
- LINE
- node2vec
- GraRep
ニューラルネットワークを利用した Embedding 手法 / GNN
Graph Embedding の手法として、次元圧縮を利用した手法とグラフ構造に着目した手法がある.
これらは、各ノードのベクトル表現を目的関数の最適化などによって学習する浅い Embedding のアプローチであった.
このようなアプローチの欠点としては、以下のものが指摘されている.
これに対して、より深い Embedding のモデルとして、GNN を用いるアプローチがある.
GNN は、グラフの構造だけでなく、各ノードの持つ属性も反映させた表現を学習するニューラルネットワークである.
GNN のメリットとして、ノードの持つ属性を入力として用いることができる.
また、出力に、ノードの表現だけでなく、エッジの表現や、グラフ全体の表現も得ることできる.
参考
- A Survey on Network Embedding
- [2017]
- arxiv.org
書籍
グラフニューラルネットワーク PyTorch による実装
- 2 グラフエンべディング
- 2.1 グラフエンべディング手法の概観
- 2.2 次元縮約に基づく手法
- 2.3 グラフ構造に基づく手法
- 2.4 ニューラルネットワークに基づく手法
-
- 2 グラフエンべディング
Python 機械学習プログラミング Pytorch & Scikit-Learn 編
- 18 グラフニューラルネットワーク
- 18.2 グラフ畳み込み
- 18 グラフニューラルネットワーク