個人の興味関心の備忘録として記録したものであり、情報の正確性や完全性を保証するものではありません。
目次
論文：Representation Learning on Graphs: Methods and Applications
三行まとめ
- グラフ表現学習は、ノードや構造をベクトルとして学習することで、分類や予測を可能にする枠組み
- 近年は GNN により、局所構造・属性・時間情報まで扱えるようになり、実問題への適用が進んでいる
- 一方で、スケーラビリティや理論的理解、動的グラフへの対応は今後の重要な課題である
イントロ
グラフは多くの分野で広く用いられている汎用的なデータ構造。
例えば、SNS、分子構造、レコメンドシステムなど数えきれない領域がグラフで容易にモデル化でき、個々の要素（ノード）間の相互作用（エッジ）を捉える。
機械学習においても、グラフ構造化データを特徴量情報として用いて予測やパターン発見を行う。
グラフ機械学習の課題は、グラフ構造の情報を機械学習モデルにどう取り込むかという点にある
左図：ノードの全体的な位置関係を強調。同じコミュニティは同じ色
右図：ノード間の構造的同質性を強調。同じ役割を持つノードが同じ色
- リンク予測では、ノード間の関係強度や共通の友人数など、二点間の特性の符号化
- ノード分類なら、ノードのグラフ内での位置や、ノードが属する周りの構造を特徴に組み込みたい
機械学習の観点では、高次元で非ユーグリット的なグラフ構造情報をベクトルに落とし込むいい方法がない。
一般的には、以下の手法を使うことが多いが、柔軟性に乏しいなどの問題が存在。
- 要約統計量（次数、クラスタリング係数）
- カーネル関数（２つのグラフ間の類似性を定量的に評価）
- 局所近傍特徴（次数、密度、中心性など）
グラフ構造の情報そのものを埋め込み表現に学習的に取り込もうとする手法が発展。（表現学習）
ノードやグラフ関係を低次元ベクトル空間に写像する関数を学習する。
この写像を最適化することで、空間内の関係が元のグラフ構造を忠実に表現できるようにする。
得られたベクトル埋め込みを下流の機械学習タスクの特徴量として利用可能。
記法と前提条件
表現学習アルゴリズムへの主な入力が、無向グラフ $G = (V,E)$および、
それに対応するバイナリ隣接行列$A$であると仮定。
ノードに関連付けられたテキストやメタデータを表現する、実数値のノード属性行列$X$も利用可能であると仮定。
EmbeddingNodes
ノード埋め込み手法(node embedding)の目的は、ノードを低次元のベクトルとして符号化し、グラフ内での位置や、そのノードの局所的なグラフ構造を要約すること。
低次元埋め込みは、ノードを潜在空間に符号化または射影したものと見ることが出来るので、
この空間の中での位置や距離、角度の関係は、元のグラフ内の相互関係(エッジとか)に対応している
A. Zachary空手クラブのソーシャルネットワークのグラフ構造。
ノードは人を表し、友人関係であればエッジが繋がっている。
異なるコミュニティごとに色分けがされている。
B. DeepWalk手法を用いて生成されたノード埋め込みの2次元可視化
埋め込み空間におけるノード間の距離は、元のグラフにおける類似性を反映しており、ノードの埋め込みは色分けされた異なるコミュニティごとに空間的にまとまっている。
手法の概要：エンコーダ・デコーダ
近年、ノード埋め込みに関する研究が急増しているが、まず「エンコーダ・デコーダ」について理解する。
- エンコーダ(Encoder)：各ノードを低次元のベクトル(埋め込み)に変換する関数
- デコーダ(decoder):学習された埋め込みから、グラフ構造情報を復元する関数
エンコーダはノード$v_i$を、グラフ上の位置や局所的な近隣構造、属性情報に基づいて、低次元のベクトル埋め込みに$z_i$に変換する。
次にデコーダが低次元ベクトルから、ノード$v_i$の近隣ノードどうなっているか、関連づけられた分類ラベルなどの情報を取り出す。
エンコーダとデコーダを同時に最適化することで、グラフ構造に関する情報を低次元の埋め込み空間に圧縮する方法を学習。
エンコーダ：$ENC : V \rightarrow \mathbb{R}^d$
ノード集合$V$の各ノードを、ベクトル埋め込み$z_i \in \mathbb{R}^d$に写像
（グラフ上のノードを、$d$次元の数値ベクトルで表現するということ）
デコーダ : $DEC : \mathbb{R}^d × \mathbb{R}^d \rightarrow \mathbb{R}^{+}$
2つのノード埋め込みペアを入力として、類似度を算出。
この類似度は、元のグラフにおける2つのノードの類似度を表す。
ノードどうしの間に繋がりが存在するかを予測したり、ノードがどのコミュニティに属しているかを予測したりする。
ノードどうしの関係性を知るために、埋め込みベクトルのペアを使って、元のグラフにおける類似度を再現しようとする。
具体的には、ノード$v_i$と$v_i$をそれぞれベクトル$z_i$と$z_i$に変換して、デコーダ関数に入力する。
デコーダの出力が、実際のグラフでの類似度にできるだけ近づくように、エンコーダとデコーダを学習
$DEC(ENC(v_i),ENC(v_j)) = DEC(z_i,z_j) \approx s_G(v_i,v_j)$
たとえば、
- $s_G(v_i,v_j) = A_{ij}$として、ノードが隣接していれば類似度1、そうでなければ0とする方法
- グラフG上でランダムウォークした時に、ノード$v_i$と$v_j$が一緒に現れる確率を使う方法
デコーダの類似と実際の類似度の差異を測定する。
エンコーダ・デコーダを最適化した後は、学習済みのエンコーダーを使って、ノードの埋め込みを作成可能。
このベクトルになっているノード埋め込みは、下流の機械学習のタスクの特徴量として利用することが可能。
ノードが属するコミュニティやネットワークのリンク推薦も可能。
最適化と実装に関する補足
最適化には確率的勾配降下法(SGD)が用いられるが、一部のアルゴリズムでは行列分解による閉形式が可能なものも存在
デコーダで測った近さと、実際の距離がどうなのか最適化していく。
Shallow型埋め込みアプローチ
シャロー型とは、ノードを多段化にの処理(ニューラルネットワーク)を通さず、ただ１つのベクトルに変換すること。
シャロー型埋め込みは「各ノードに一つのベクトルを割り当てるだけ」の単純で直感的なモデル。
$ENC(v_i) = Zv_i$
- $Z \in \mathbb{R}^{d \times |V|} $ : 全ノードの埋め込みベクトルを含む行列
- $v_i \in \mathbb{I}^{|V|}$：ノード$v_i$に対するワンホットベクトル
$Z$：全ノードの埋め込みベクトルを含む行列
Z =
\begin{bmatrix}
0.1 & 0.5 & -0.4 & 0.3 \\
-0.2 & 0.0 & 0.7 & 0.8 \\
0.3 & -0.1 & 0.2 & -0.6
\end{bmatrix}
ノード$v3$に対応するワンホットベクトルは、
v_3 =
\begin{bmatrix}
0 \\
0 \\
1 \\
0
\end{bmatrix}
ノード$v3$の埋め込みベクトルの求め方
\text{ENC}(v_3) = Z v_3 =
\begin{bmatrix}
0.1 & 0.5 & -0.4 & 0.3 \\
-0.2 & 0.0 & 0.7 & 0.8 \\
0.3 & -0.1 & 0.2 & -0.6
\end{bmatrix}
\cdot
\begin{bmatrix}
0 \\
0 \\
1 \\
0
\end{bmatrix}
=
\begin{bmatrix}
-0.4 \\
0.7 \\
0.2
\end{bmatrix}
多くのシャロー型埋め込み手法はもともと行列分解アルゴリズムとして提案されていて、
エンコーダ・デコーダの枠組みで再解釈している。
行列分解に基づくアプローチ
ノード表現(埋め込み)を学習する初期の手法は、主に行列分解に焦点を当てていて、古典的な次元削除手法に触発されている。
- ラプラシアン固有写像
最も初期かつ有名な手法の一つ。
デコーダは以下のように定義される。
\text{DEC}(z_i, z_j) = \| z_i - z_j \|^2
ノード$i$とノード$j$のベクトルのユーグリット距離の2乗
損失関数は、ノードの類似度に応じてペアの重みをつけて最小化
L = \sum_{(v_i, v_j) \in D} \| z_i - z_j \|^2 \cdot s_G(v_i, v_j)
似ているノードほど、埋め込み空間でも近づけるように学習
（※LLMの時もこんなことしてなーー なんの手法か忘れてしまった）
- 内積ベースの手法
ノードペア間の内積を使ったデコーダ
DEC(z_i,z_j) = z_i^\top z_j
ベクトルの距離ではなく、向きの近さに着目して、ノード間の関係性を捉えたもの。
ノード間の関係の強さが、それぞえれの埋め込みベクトルの内積に比例するような手法も存在。
Graph Factorization・GraRep・HOPEが該当
これら3つの手法は全て、内積を用いたデコーダと平均二乗誤差損失を使用している。
L = \sum_{(v_i, v_j) \in D} \left\| \text{DEC}(z_i, z_j) - s_G(v_i, v_j) \right\|^2
３つの手法の違いは、$s_G(v_i, v_j) $の設計
- Graph Factorozationは、類似度を隣接行列(繋がりがあれば1、なければ0)に基づいている
- GraRepは、より高次のノードの類似性を捉えるために、隣接行列の累乗を用いている
- Hopeは、jaccard係数による近傍の重みなどにより、より一般的な類似度指標を使えるように設計。
これらの手法は、ノード間の類似度指標を近似するような埋め込みベクトルを学習することが目的
ランダムウォークに基づくアプローチ
ランダムウォークに基づくアプローチでは、グラフ上での短いランダムウォーク中に共起しやすいノード同士が、似た埋め込みを持つように最適化を行う。柔軟で確率的なノード類似度の指標を利用している。
各ノード$v_i$を視点として、固定長のランダムウォークを多数サンプリングする。
埋め込みベクトル$z_i$と$z_j$の内積(または角度)が、ノード$j_i$から始まる固定長のランダムウォーク中のノード$j_z$に訪れる確率に比例するように最適化する
どうノードを訪れるかをパラメータで設定することで発展させることが可能。(DeepWalkやnode2vec)
パラメータを調整することで、コミュニティ構造を強調した埋め込みやノードの局所的な構造的役割を強調した埋め込みが可能となる。
Large-scale Information Network Embeddings(LINE)
ランダムウォークに基づかない別の成功した手法として、Large-scale Information Network Embeddingが存在
LINEは、一次類似度、二次類似度を最適化するエンコーダ・デコーダ目的関数を組み合わせている。
固定長ランダムウォークに頼るのではなく、一次・二次の類似度を明示的に分解して扱う。
HARP : グラフ前処理によるランダムウォーク埋め込みの拡張
グラフを縮約して、グラフの中で関連性の高いノードを1つのスーパーノードとしてまとめるメタ戦略。
まとめた後に、DeepWalk、node2vec、LINEのいずれかを、縮約されたグラフで実行する。
ランダムウォーク手法のさらなる発展
DeepWalkを拡張し、各ステップで複数のノードをスキップ/ジャンプして移動するランダムウォークを提案
一般化されたエンコーダ・デコーダアーキテクチャ
シャロー型埋め込み手法、各ノードごとに独立で埋め込みベクトルを学習するために以下のような欠点が存在
-
エンコーダ間でパラメータの共有がない
エンコーダは単に任意ノードに基づく参照なので、ノード間でパラメータが共有されない。
統計的にも非効率であり、パラメータを共有することで正則化の役割を果たす。
計算コストの面でも非効率であり、ノード数に比例してパラメータ数が増加してしまう。 -
ノード属性をエンコーディングに活用できない
ノードは属性情報(SNSにおけるユーザープロファイルなど)を持っており、これらの情報はノードのグラフ内での位置や役割に関して非常に有用であるが、シャロー型埋め込み手法では活かせない。 -
学習時に見たノードにしか使えない
学習時に存在していたノードに対してしか埋め込みを作成できず、未知のノードには新たに学習を行わない限り埋め込みを作成できない。これが、ノードが動的に変化する進化型グラフや、全体をメモリの載せられないような巨大グラフや、学習後に新しいグラフへの一般化が求められるようなドメインで非常に問題となる。
近傍オートエンコーダ手法(Neighborhood Autoencoder Methods)
Deep Neural Graph Representations(DNGR) と**Structural Deep Network Embeddings(SDNE)**は、
グラフ構造をエンコーダに直接組み込めないという点に対処している。
この手法の基本的な考え方は、オートエンコーダを用いてノードの局所的な近傍情報を圧縮する点。
- 各ノード$v_i$について、グラフ内の全ノードとの類似度を並べた高次元ベクトル$s_i \in \mathbb{R}^{|V|}$を作る
- この$s_i$をオートエンコーダに入力
- 低次元ベクトル$z_i$に圧縮(Encoder)
ノードの"近傍構造そのもの"を深層学習で圧縮している。
SDNEとDNGRは、ノードの近接構造を直接エンコーダに入力することで従来の手法を大きく前進させたが、入力次元が$|V|$に固定されるためスケーラビリティと汎化性に大きな制約が存在。
近傍集約・畳み込み型エンコーダ(Neighborhood aggregation and convolutional encoders)
グラフ全体ではなく、ノードの局所的な近傍に基づいて動作するエンコーダを設計している。
ノードの埋め込みを、その局所近傍から情報を集約することで生成する。
ノードの特徴用や属性を用いて埋め込みを作成できるので、SNSのプロフィールなどの属性情報を活用して埋め込みを作成できる。
近傍集約型エンコーダでは、ノードの埋め込みを反復的に更新する。
最初にノード埋め込みはノード属性で初期化され、各ステップで近傍ノードの埋め込みを集約し、その結果と自身の埋め込みを組み合わせて新しい表現を作る。
この処理を繰り返すことで、ノード埋め込みには徐々により広い範囲の近傍情報が取り込まれる。
一方で埋め込みの次元は固定されているため、近傍構造は低次元ベクトルに圧縮される。
GCN や GraphSAGE、Column Networks はこの枠組みに基づく手法であり、集約方法やベクトルの結合方法が異なる。
これらの手法はパラメータを全ノードで共有するため、大規模グラフでも効率的に学習でき、未知ノードにも対応できる。
タスク固有の教師信号の入力
これまでのエンコーダ–デコーダ型グラフ埋め込みは基本的に教師なし学習だが、近傍集約型手法ではノード分類などのタスク固有の教師信号を直接利用できる。
ノード埋め込みを分類器（シグモイド関数）に入力し、
予測ラベルと正解ラベルのクロスエントロピー損失を計算することで、その誤差をエンコーダに逆伝播させて学習を行う。
この教師あり損失は、デコーダによる再構成損失の代わりに用いることも、両者を組み合わせて用いることもできる。
教師なし学習ではグラフとして自然な埋め込みしか作れなかったが、タスク固有の教師信号を入れることで目的に最適化された埋め込みを学習できるようになる。
マルチモーダルグラフへの拡張
実世界のグラフは、単一種類のノードやエッジからなる単純な構造とは限らず、異なる種類のノードや関係を含むマルチモーダル（マルチレイヤー）な構造を持つことが多い。
そのため、近年ではこうした異質な構造を扱うためのグラフ埋め込み手法や GNN の拡張が数多く提案されている。
SNS では、「ユーザー」「投稿」「ハッシュタグ」といった異なる種類のノードが存在し、「フォロー」「投稿」「タグ付け」など意味の異なるエッジで結ばれている。
ノードタイプ・エッジタイプの違いへの対応
異種グラフでは、ノードやエッジの種類が異なるため、単一のエンコーダやデコーダでは構造を十分に表現できない。
一般的な対応方法は、ノードタイプごとに異なるエンコーダを使い、エッジタイプごとに専用のデコーダパラメータを持たせることである。
特に、エッジタイプごとに双線形形式のデコーダを導入することで、関係の違いを埋め込み空間に反映できる。
また、ランダムウォークの遷移をノードタイプで制限することで、DeepWalk や node2vec などの手法を異種グラフに拡張するアプローチも提案されている。
レイヤー間でのノード埋め込みの共有
マルチレイヤーグラフでは、同じノードが複数のレイヤーに登場することがある。
この場合、レイヤーごとに独立して埋め込みを学習すると、本来共有できる情報が失われてしまう。
OhmNetは、異なるレイヤーにおける同一ノードの埋め込みが大きく乖離しないよう正則化をかけることで、レイヤー間で情報を共有する手法である。
さらに、レイヤー間に階層構造がある場合には、親子レイヤー間でも同様の正則化を適用し、粗いレベルから詳細なレベルまで一貫した表現を学習する。
構造的役割の埋め込み
これまでの多くのグラフ埋め込み手法は、「近いノードほど似た表現になる」ことを重視してきた。
しかし、通信網や交通網などでは、位置とは無関係に、同じ役割を持つノードを同一視したい場合がある。
この目的のために、struc2vecやGraphWave といった構造的役割の学習に特化した手法が提案されている。
struc2vec は近傍の次数構造に基づいて構造的に似たノードを結び直し、GraphWave はスペクトル情報を用いてノードの局所トポロジーを表現する。
これらの手法により、グラフ上で離れていても同じ役割を持つノードを近い埋め込みとして表現することが可能になる。
ノード埋め込みの応用
ノード埋め込みは、可視化・クラスタリング・分類・リンク予測といった多くの下流タスクで利用されている。
ノードをベクトルとして表現することで、t-SNE や PCA による可視化、k-means などの汎用クラスタリング手法をそのまま適用できる点が大きな利点である。
また、ノード分類では少数のラベルからグラフ全体を推定する半教師あり学習が一般的であり、近年では未知ノードを扱う inductive な設定も重要になっている。
さらに、リンク予測はレコメンドシステムや知識グラフ補完、生物ネットワーク解析などで中核的な応用となっている。
サブグラフの埋め込み
サブグラフ埋め込みでは、ノード単体ではなく、ノード集合とエッジ集合からなる部分グラフ全体を1つのベクトルとして表現することを目的とする。
この表現は、分子グラフの性質予測など、グラフ単位での判断が必要なタスクに用いられる。
多くの手法では、まずノード埋め込みを学習し、その後、サブグラフに含まれるノード埋め込みを和やプーリングなどの方法で集約することでサブグラフ全体の表現を構築する。
より高度な手法では、畳み込みとグラフの縮約（coarsening）を繰り返すことで、局所構造から大域構造までを段階的に統合する。
また、GNN や Message Passing Neural Networks（MPNN）を用いることで、ノード間の情報伝播を通じてサブグラフ表現を学習することも可能。
サブグラフ埋め込みは教師あり学習として扱われることが多く、特に分子設計や薬効予測、材料探索といった分野で重要な役割を果たしている。
ノード埋め込みに比べて、より直接的に「グラフ全体の意味」を捉えられる点が特徴。
- 時間変化などの動的変化を考慮したグラフを考える必要がありそう
- グラフ構造を学習しているときの解釈性を上げる方法とか存在していないのか