オムライスの備忘録

数学・統計学・機械学習・プログラミングに関することを記す

【グラフ処理】Graph Embedding

Index

Graph Embedding

Graph Embedding とは、グラフの各ノードの構造情報を低次元のベクトルで表現する手法.

グラフの表現学習 / Representation Learning とも呼ばれる.



ノード集合  V、エッジ集合  E のグラフ  G\ =\ (V,\ E) において、 各ノード  v\ \in\ V に対して、ノード数  |V| よりも小さい  k 次元表現  r_{v}\ \in\ R^{k} を取得する.



その際、グラフ上での近接性が保たれる必要がある.

すなわち、グラフ上で近いノード同士のベクトル表現も近くなければならない.

従来のグラフ表現における課題

  • 高い計算コスト
  • 低い並列度
  • 機械学習手法の適用不可

これらの課題に対応するために、グラフ情報を低次元のベクトルで表現することがモチベーションになる.

次元圧縮

高次元データから低次元の表現を得る古典的な方法として、次元圧縮がある.

  • 主成分分析 / PCA
  • 多次元尺度構成法 / MDS
  • 特異値分解 / SVD
  • lsomap

これらはいずれも、高次元データから低次元データの表現を得る一般的な手法であるが、 多くのグラフ表現においては構造情報だけでなく、各ノードやエッジが情報を持っている場合もある.

それらの情報を含めての次元圧縮という意味では、これらの手法は十分とはいえない.

グラフ構造に着目した Embedding 手法

  • DeepWalk
  • LINE
  • node2vec
  • GraRep

ニューラルネットワークを利用した Embedding 手法 / GNN

Graph Embedding の手法として、次元圧縮を利用した手法とグラフ構造に着目した手法がある.

これらは、各ノードのベクトル表現を目的関数の最適化などによって学習する浅い Embedding のアプローチであった.

このようなアプローチの欠点としては、以下のものが指摘されている.

  1. 浅い Embedding は、エンコードの際に、ノード間でパラメータを共有しない.


  2. 浅い Embedding では、エンコードの際に、ノードの特徴を用いない.


  3. 浅い Embedding は transductive な (特定の事例から特定の事例への) ものであり、訓練時に存在するノードについての Embedding した生成できない.



これに対して、より深い Embedding のモデルとして、GNN を用いるアプローチがある.

GNN は、グラフの構造だけでなく、各ノードの持つ属性も反映させた表現を学習するニューラルネットワークである.

GNN のメリットとして、ノードの持つ属性を入力として用いることができる.

また、出力に、ノードの表現だけでなく、エッジの表現や、グラフ全体の表現も得ることできる.

参考

  • A Survey on Network Embedding

書籍