データマイニング - グラフ埋め込み入門

1. スペクトラルクラスタリング
2. ランダムウォーク × 埋め込み
3. グラフニューラルネットワーク

Transcript

1. グラフ埋め込み ⼭本 祐輔 名古屋市⽴⼤学 データサイエンス研究科 yusuke_yamamoto@acm.org 第14回 データマイニング （グラフ分析入門） ⼭本祐輔 クリエイティブコモンズライセンス (CC BY-NC-SA 4.0)
2. 講義資料 https://b.hontolab.org/graph-analysis
3. 典型的なグラフ分析のタスク（1/2） 最短経路発⾒ コミュニティ発⾒ ノード中⼼性評価
4. 典型的なグラフ分析のタスク（2/2） ノード分類 ノード間の関係性予測 つながる? ⻘, 緑, 黒? 友達 友達 友達 先輩-後輩 何関係? エッジ分類 これは何のグラフ? グラフ分類
5. タスクに応じたグラフ分析⼿法の例 コミュニティ発⾒ ノード中⼼性評価 分析 近接中⼼性, 媒介中⼼性, 固有ベクトル中⼼性, PageRank, … 分析 連結成分抽出, Girvan-Newman法, リンクコミュニティ法, …
6. タスク再考 コミュニティ発⾒ ノード分類 ⻘, 緑, 黒? ノードのクラスタリング （教師なし学習） ノードの分類問題 （教師あり学習） 汎用的な機械学習手法が使えないのか？
7. グラフ分析 と 汎⽤機械学習 グラフ ベクトル 汎⽤機械学習⼿法 適⽤ グラフ分析⼿法 適⽤ 変換 変換 𝑥!,! 𝑥!,# … 𝑥!,!$ 𝑥#,! 𝑥#,# … 𝑥#,!$ ⋮ ⋮ ⋱ ⋮ 𝑥!$,! 𝑥!$,# … 𝑥!$,!$ グラフ-ベクトル間で変換できれば，それぞれの手法が使える!!
8. 例: リンク予測（=ノード間の関係性予測）
9. 例: リンク予測（=ノード間の関係性予測） フォローを おすすめ?
10. ベクトル化ができれば（1/2） フォローを おすすめ? Type equation here. 𝑣!" = 3.14 −1.59 ⋮ 2.65 𝑣#$ = 2.71 −8.28 ⋮ 1.82
11. ベクトル化ができれば（2/2） 𝑿 = 1.41 ⋯ 4.21 1.73 ⋯ 2.05 1.41 ⋯ 4.21 −2.23 ⋯ −6.06 ⋱ −3.16 ⋯ −2.27 1.73 ⋯ 2.05 −3.16 ⋯ −2.27 −2.23 ⋯ −6.06 ノードのベクトル ノードのベクトル ノードのベクトル ノードのベクトル 𝒚 = 1 0 ⋮ 0 1 から にエッジが張られている から にはエッジが張られていない
12. ベクトル化さえできれば，汎⽤機械学習でリンク予測が可能 # Python 1 from sklearn import svm 2 import numpy as np 20 model = svm.SVC(kernel=‘poly’) # 分類器にSVMを指定 21 model.fit(X, y) # SVMで分類器を学習 # リンク元とリンク先のベクトルを結合 22 X_target = np.concatenate([v_⼭, v_to]) # 学習済みのSVMを使ってリンク予測 23 will_be_linked = model.predict(X_target) >> [1] # リンクが張れると予測 …
13. グラフ埋め込み (Graph Embedding) A C N次元の埋め込み空間 グラフ B 𝒗3 𝒗4 𝒗5 埋め込み グラフあるいはその要素を低次元の密ベクトルに変換したもの グラフ埋め込み表現 表現学習 データから質の良い埋め込み表現を獲得するためのタスク 良い埋め込み表現は、埋め込み空間上で似たノード同士を近くに配置する
14. グラフをベクトル化する超単純な⽅法 0 2 3 4 1 5 10 8 7 6 9 𝑨 = 0 1 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 隣接行列の各行を各ノードのベクトルと見なす 𝒗6 = 0,1,1,0,1,0,0,0,0,0,0 7 𝒗8 = 0,0,0,0,0,0,0,1,0,1,0 7 ノード0の隣接関係 ノード6の 隣接関係
15. グラフをベクトル化する超単純な⽅法 0 2 3 4 1 5 10 8 7 6 9 𝑨 = 0 1 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 隣接行列の各行を各ノードのベクトルと見なす 𝒗6 = 0,1,1,0,1,0,0,0,0,0,0 7 𝒗8 = 0,0,0,0,0,0,0,1,0,1,0 7 𝑠𝑖𝑚39:(𝒗6, 𝒗8) = 0 類似度ゼロ (遠く離れているので妥当)
16. グラフをベクトル化する超単純な⽅法 0 2 3 4 1 5 10 8 7 6 9 𝑨 = 0 1 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 隣接行列の各行を各ノードのベクトルと見なす 𝒗6 = 0,1,1,0,1,0,0,0,0,0,0 7 𝒗; = 1,0,1,0,1,0,0,0,0,0,0 7 𝑠𝑖𝑚39:(𝒗6, 𝒗;) = 0.667 類似度⾼い (つながりが似ているので妥当)
17. グラフをベクトル化する超単純な⽅法 0 2 3 4 1 5 10 8 7 6 9 𝑨 = 0 1 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 隣接行列の各行を各ノードのベクトルと見なす 𝒗< = 1,1,1,1,0,1,0,0,0,0,0 7 𝒗= = 0,0,0,0,1,0,0,1,0,0,1 7 𝑠𝑖𝑚39:(𝒗<, 𝒗=) = 0 類似度ゼロ (隣り合っているのに!?) 何が問題なのか？
18. 隣接⾏列の⾏をノードのベクトルと⾒なす問題点 0 2 3 4 1 5 10 8 7 6 9 𝑨 = 0 1 1 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 行列のスパース性 隣接⾏列の⼤部分は値がゼロ（世の中の⼤抵のグラフはスパース（疎）） グラフの特徴の捉え方が不十分 ノードの構造的特徴は隣接ノードだけでは決まらない （グラフにおける相対的な位置づけを⾒ていない） どうすれば密で特徴を捉えた良質な埋め込みが得られるか？ スパース!! スパース!!
19. スペクトラルクラスタリング 1 古典的なグラフ埋め込み⼿法
20. スペクトラルクラスタリング（Spectral Clustering） l グラフ埋め込みにおける古典的⼿法 l ⾮グラフデータのクラスタリング⼿法として提案 l ノード間の接続関係に注⽬ 0 2 3 4 1 5 10 8 7 6 9 𝑿 = 0.327 0.082 0.091 0.327 0.082 0.091 0.327 0.082 0.091 0.327 0.082 0.091 0.257 0.055 −0.076 −0.078 −0.074 −0.603 −0.410 0.322 0.202 −0.322 0.214 −0.171 −0.193 −0.702 0.533 −0.410 0.322 0.203 −0.152 −0.467 −0.450 Spectral clustering
21. スペクトラルクラスタリングの問題設定 0 2 3 4 1 5 10 8 7 6 9 各ノードに何らかの数値を割り当てたいが、 隣接しているノードにはできる限り近い値を割り当てる 𝑥! = 0.32 𝑥" = −0.41 𝑥# = 0.32 𝑥$ = 0.25 |𝑥! − 𝑥" | = 0.32 − 0.32 = 0 |𝑥! − 𝑥# | = 0.32 − 0.25 = 0.07 |𝑥! − 𝑥$ | = 0.32 − (−0.41) = 0.73 理想的な割り当ての例 隣接するノードは 差が⼩さい 隣接しないノードは 差が⼤きい
22. スペクトラルクラスタリングの問題設定 0 2 3 4 1 5 10 8 7 6 9 各ノードに何らかの数値を割り当てたいが、 隣接しているノードにはできる限り近い値を割り当てる 𝐿(𝒙) = 7 %,'∈)! 𝐴%,' |𝑥% − 𝑥' | 問題定義 ノードiとjの 割当値の差を⾒る
23. スペクトラルクラスタリングの問題設定 0 2 3 4 1 5 10 8 7 6 9 各ノードに何らかの数値を割り当てたいが、 隣接しているノードにはできる限り近い値を割り当てる 𝐿(𝒙) = 7 %,'∈)! 𝐴%,' |𝑥% − 𝑥' | 問題定義 ただし，iとjが隣接 している時のみ注⽬する （Ai,j は隣接⾏列Aの(i,j)要素の値 で隣接していたら1，隣接して いなかったら0となる）
24. スペクトラルクラスタリングの問題設定 0 2 3 4 1 5 10 8 7 6 9 各ノードに何らかの数値を割り当てたいが、 隣接しているノードにはできる限り近い値を割り当てる 𝐿(𝒙) = 7 %,'∈)! 𝐴%,' 𝑥% − 𝑥' * 問題定義 絶対値を⾒ても ⼆乗を⾒ても同じ
25. スペクトラルクラスタリングの問題設定 0 2 3 4 1 5 10 8 7 6 9 各ノードに何らかの数値を割り当てたいが、 隣接しているノードにはできる限り近い値を割り当てる 𝐌𝐢𝐧𝐢𝐦𝐢𝐳𝐞 𝐿(𝒙) = 7 %,'∈)! 𝐴%,' 𝑥% − 𝑥' * 問題定義 s. t. 𝑥# % + 𝑥% % + ⋯ + 𝑥& % = 𝒙 % = 1 全ノードの組み合わせ について調べる
26. スペクトラルクラスタリングの問題設定 0 2 3 4 1 5 10 8 7 6 9 各ノードに何らかの数値を割り当てたいが、 隣接しているノードにはできる限り近い値を割り当てる 𝐌𝐢𝐧𝐢𝐦𝐢𝐳𝐞 𝐿(𝒙) = 7 %,'∈)! 𝐴%,' 𝑥% − 𝑥' * 問題定義 s. t. 𝑥# % + 𝑥% % + ⋯ + 𝑥& % = 𝒙 % = 1 値が無限に⼤きくならないよう 制約を与える
27. スペクトラルクラスタリングの問題設定 0 2 3 4 1 5 10 8 7 6 9 各ノードに何らかの数値を割り当てたいが、 隣接しているノードにはできる限り近い値を割り当てる 𝐌𝐢𝐧𝐢𝐦𝐢𝐳𝐞 𝐿(𝒙) = 7 %,'∈)! 𝐴%,' 𝑥% − 𝑥' * 問題定義 s. t. 𝑥# % + 𝑥% % + ⋯ + 𝑥& % = 𝒙 % = 1 最小化問題に帰着させる
28. 式変形 (1/2) 𝐿 𝒙 = 7 %,'∈)! 𝐴%,' 𝑥% − 𝑥' * = 7 %,'∈)! 𝐴%,' (𝑥% * − 2𝑥% 𝑥' + 𝑥' *) = 7 %,'∈)! 𝐴%,' (𝑥% * + 𝑥' *) − 2 7 %,'∈)! 𝐴%,' 𝑥% 𝑥' 𝐴>? = 𝐴?> 無向グラフの場合, Aは対称⾏列なので @ %,&∈(! 𝐴%,& 𝑥% # = @ %,&∈(! 𝐴%,& 𝑥& # このとき
29. 式変形 (1/2) 𝐿 𝒙 = 7 %,'∈)! 𝐴%,' 𝑥% − 𝑥' * = 7 %,'∈)! 𝐴%,' (𝑥% * − 2𝑥% 𝑥' + 𝑥' *) = 7 %,'∈)! 𝐴%,' (𝑥% * + 𝑥' *) − 2 7 %,'∈)! 𝐴%,' 𝑥% 𝑥' = 7 %,'∈)! 𝐴%,' (2𝑥% *) − 2 7 %,'∈)! 𝐴%,' 𝑥% 𝑥' = 2 7 %,'∈)! 𝐴%,' 𝑥% * − 7 %,'∈)! 𝐴%,' 𝑥% 𝑥' 先にjに関する和を取ると 6 '∈)! 𝐴*,' = 6 '∈)! 𝐷*,* (D は次数⾏列) 6 *,'∈)! 𝐴*,' 𝑥* % = 6 *∈)! 𝐷*,* 𝑥* %
30. 式変形 (2/2) 𝐿 𝒙 = 2 7 %,'∈)! 𝐴%,' 𝑥% * − 7 %,'∈)! 𝐴%,' 𝑥% 𝑥' = 2 7 %,'∈)! 𝐷%,% 𝑥% * − 7 %,'∈)! 𝐴%,' 𝑥% 𝑥' = 2 𝒙/𝑫𝒙 − 𝒙/𝑨𝒙 = 2𝒙!𝓛𝒙 ℒ = 𝐷 − 𝐴 : 次数⾏列 : 隣接⾏列 : グラフラプラシアン ただし， ℒ 𝐷 𝐴
31. スペクトルクラスタリングにおける最適化問題 𝐌𝐢𝐧𝐢𝐦𝐢𝐳𝐞 𝐿(𝒙) = 7 %,'∈)! 𝐴%,' 𝑥% − 𝑥' * s. t. 𝑥# % + 𝑥% % + ⋯ + 𝑥& % = 𝒙 % = 1 = 2𝒙+𝓛𝒙 ラグランジュの未定乗数法 𝜕 𝜕𝒙 2𝒙+𝓛𝒙 − 𝜆′ 𝒙𝑻𝒙 − 1 = 2𝓛𝒙 − 2𝜆𝒙 = 0 となる x を求める問題になる． 𝓛𝒙 = 𝜆𝒙 これは となる x を求める問題，つまり 𝓛の固有値問題に帰着される
32. グラフラプラシアンの固有値と固有ベクトル 𝓛𝒙 = 𝜆𝒙 2𝒙!𝓛𝒙 = 2𝒙!𝜆𝒙 = 2𝜆𝒙!𝒙 = 2𝜆 2𝒙!𝓛𝒙 = 𝐿 𝒙 = 2𝜆 両辺に左から2xTをかける 制約条件 |x|2 = xTx =1を思い出す そもそも我々はL(x)= 2𝒙)𝓛𝒙 の最⼩化問題を解いていた 固有値 λ は目的関数の最小値 （の候補）、 固有ベクトル x はノードに割当値（の候補）を示している
33. 0.302 0.327 0.082 0.091 ⋯ −0.168 0.302 0.327 0.082 0.091 ⋯ −0.168 0.302 0.327 0.082 0.091 ⋯ −0.168 0.302 0.327 0.082 0.091 ⋯ −0.168 0.302 0.257 0.055 −0.076 ⋯ 0.866 0.302 −0.078 −0.074 −0.603 ⋯ −0.339 0.302 −0.410 0.322 0.203 ⋯ −0.024 0.302 −0.322 0.214 −0.171 ⋯ 0.122 0.302 −0.193 −0.702 0.533 ⋯ −0.017 0.302 −0.410 0.322 0.203 ⋯ −0.024 0.302 −0.152 −0.467 −0.450 ⋯ 0.085 スペクトラルクラスタリングによるグラフ埋め込みの⼿順 1. 2. グラフGのラプラシアンℒ (= D – A )を取得 ラプラシアンℒを固有値と固有ベクトルを得る 3. 固有ベクトル uを固有値の⼩さい順に横に k個並べた⾏列をノード埋め込み⾏列とする 𝓛 = 3 −1 −1 0 −1 0 0 0 0 0 0 −1 3 −1 0 −1 0 0 0 0 0 0 −1 −1 4 −1 −1 0 0 0 0 0 0 0 0 −1 2 −1 0 0 0 0 0 0 −1 −1 −1 −1 5 1 0 0 0 0 0 0 0 0 0 −1 3 0 −1 0 0 −1 0 0 0 0 0 0 2 −1 0 −1 0 0 0 0 0 0 −1 −1 3 0 −1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 −1 −1 0 2 0 0 0 0 0 0 −1 0 0 −1 0 2 𝑿 = 𝒖$ , 𝒖! , … , 𝒖* = 固有値 計算 最も⼩さい固有値に 対応する固有ベクトル (全ノードが1つのグループに) 2番⽬から2+k番⽬に⼩さい固有値に 対応する固有ベクトル ⼤きい固有値に対応 する固有ベクトルは無視
34. 例: Karatte club graph スペクトラル クラスタリングで 2次元空間に埋め込み
35. 例: Karatte club graph スペクトラル クラスタリングで 2次元空間に埋め込み K-means クラスタリング
36. 例: Karatte club graph スペクトラル クラスタリングで 2次元空間に埋め込み K-means クラスタリング
37. ランダムウォーク × 埋め込み 2 ⾃⼰教師あり学習による表現学習
38. 単語埋め込み (Word Embedding) 単語の潜在的な意味を捉えるために、 単語を低次元の密ベクトルに変換する技術 - 単語の意味の類似性や単語間の関係性が演算可能に - 単語埋め込みは機械による⽂章理解のための基礎 (e.g. Transformer) 類似性の演算 ⼥ 男 冷蔵庫 近い 遠い 𝑑𝑖𝑠𝑡 𝑣男, 𝑣⼥ < 𝑑𝑖𝑠𝑡(𝑣男, 𝑣冷蔵庫) 関係性の演算 ⼥ 男 王 𝑣⼥ − 𝑣男 + 𝑣王 = 𝑣⼥王 ⼥王 ベクトル演算 どうやって意味ベクトルを獲得するのか？
39. Harrisの分布仮説 単語の意味は、その周囲に現れる単語によって決まる 仮説 海 で 釣った 魚 を 刺⾝ にして ⾷べる ⽔族館 は 海獣 や 魚 との 距離 が 近い アジ は 回遊 魚 で ⽇本 各地 で 釣れる Harris, Z. (1954). Distributional structure. Word, 10(23): 146-162.
40. Word2Vec（1/2） Mikolov, T., Sutskever, I., Chen, K., Corrado, G. S., & Dean, J. (2013). Distributed representations of words and phrases and their compositionality. Advances in neural information processing systems, 26. 分布仮説をニューラルネットワークによる分類問題に 帰着し、単語の埋め込み表現を得る手法 海 で 釣った ? を 刺⾝ にして ⾷べる 𝑃 ⿂ 海, 釣り, 刺⾝, ⾷べる = 𝑓(𝑣S ⿂ , ⽂脈ベクトル) 𝑣, 海 + 𝑣, 釣り +𝑣, 刺⾝ + 𝑣, (⾷べる) 確率が高くなるよう全単語のベクトルの値を調整する 周囲の単語から単語を予測 するモデルを学習(C-BoWモデル)
41. Word2Vec（2/2） Mikolov, T., Sutskever, I., Chen, K., Corrado, G. S., & Dean, J. (2013). Distributed representations of words and phrases and their compositionality. Advances in neural information processing systems, 26. 海 で 釣った ? を 刺⾝ にして ⾷べる アジ は 回遊 ? で ⽇本 各地 で 釣れる 海 で 釣った ⿂ を ？ にして ⾷べる … 大量の文書を使って 埋め込みベクトルと単語予測の学習を行う
42. Word2Vec × グラフ埋め込み 海 → 釣った → ⿂ → 刺⾝ 単語の系列 Word2Vec 単語の 埋め込み表現 𝑣S ⿂ = (3.5, −2.7, … , 6.1) グラフ 変換!? ノードの系列 Word2Vec ノードの 埋め込み表現 𝑣T • = (3.5, −2.7, … , 6.1) どうやってグラフをノード系列に変換するか？
43. グラフ上のランダムウォーク 0 2 3 4 1 5 10 8 7 6 9 0 2 3 4 1 5 10 8 7 6 9 1/4 1/4 1/4 1/3 1/3 1/3 4へ遷移 隣接ノードから遷移するノードを確率的に選択する 0 2 3 4 1 5 10 8 7 6 9 1/4 0 2 3 4 1 5 10 8 7 6 9 3へ遷移 4へ遷移 1/2 1/2
44. ランダムウォークによるノード系列の⽣成 0 2 3 4 1 5 10 8 7 6 9 0 → 2 → 4 → 1 → 2 4 → 5 → 10 → 5 → 7 3 → 2 → 4 → 5 → 4 5 → 7 → 9 → 7 → 6 2 → 0 → 1 → 0 → 1 … ノード系列 グラフ 任意の出発ノードからランダムウォークを繰り返すことで 任意の長さのノード系列を無限に生成
45. Hands-on タイム 以下のURLにアクセスして， 第14回のクイズQ1を解いてみよう https://graphnote.hontolab.org/ 45
46. DeepWalk Perozzi, B., Al-Rfou, R., & Skiena, S. (2014, August). Deepwalk: Online learning of social representations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 701-710). ランダムウォークとWord2Vecを用いて グラフ中のノードの埋め込み表現を得る手法 1. グラフGのノード集合Vからノードvを取得 2. ノードvを起点としたランダムウォークを⾏い， ⻑さTのノード系列 l を得る 3. ステップ1-2をノード集合V のすべてのノードに 対しN回繰り返しノード系列集合Lを得る 4. ノード系列集合Lに対してWord2Vecを適⽤
47. DeepWalkの⽋点 サンプリングバイアス ランダムウォークによるノードサンプリングでは，⼀部の ノードの出現頻度に意図しない偏りが出る可能性がある グラフ構造の局所性に敏感 - グラフやタスクの性質に応じて注⽬するグラフ構造は異なる - 単純なランダムウォークでは，出発ノードの近傍ノード （局所的構造）を中⼼にサンプリングされてしまう スペクトラルクラスタリングも局所性に敏感
48. グラフ構造から⾒える（⾒たい）ノードの傾向 ホモフィリー 俯瞰したときに、類似の コミュニティに属している？ 構造的同値性 他のノード群と 接続パターンが類似している？ ノードの⼤域的関係性 に注⽬する必要アリ ノードの局所的関係性 に注⽬する必要アリ タスクに応じてどちらを重視するか制御したい
49. 深さ優先探索と幅優先探索 深さ優先探索 (DFS) 幅優先探索 (BFS) 1 2 3 4 1 2 3 4 ⼤域的関係性を掘り下げる 系列をリストアップ 局所的関係性を掘り下げる 系列をリストアップ ホモフィリーを 捉えたいタスク向き 構造的同値性を 捉えたいタスク向き
50. node2vecのアルゴリズム DFS/BFSを組み込んだランダムウォークによって ノードサンプリングを行い、ノード埋め込みを実行 node2vec: Scalable Feature Learning for Networks. A. Grover, J. Leskovec. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2016. 1. グラフGのノード集合Vからノードvを取得 2. ノードvを起点とした調整ランダムウォークを⾏い， ⻑さTのノード系列 l を得る 3. ステップ1-2をノード集合V のすべてのノードに 対しN回繰り返しノード系列集合Lを得る 4. ノード系列集合Lに対してWord2Vecを適⽤ 0. ランダムウォークパラメータp, qを設定
51. DeepWalkにおけるランダムウォークの遷移確率 vt 𝜋8!,8!"# = / 1 0 𝑣U, 𝑣UV; ∈ 𝐸の場合 上記以外の場合 Pr(𝑣;<= |𝑣; ) = 𝜋8!,8!"# ∑ 8∈>?@ABCDEFG(8!) 𝜋8!,8 ただし （つまり隣接） 1/4 1/4 1/4 1/4 vt+1 vt+1 vt+1 vt+1
52. node2vecにおけるランダムウォークの遷移確率 𝜋-",-"#$ = . / 1 . 0 0 𝑣U, 𝑣UV; ∈ 𝐸かつ𝑑 𝑣UW;, 𝑣UV; = 0の場合 𝑣U, 𝑣UV; ∈ 𝐸かつ𝑑 𝑣UW;, 𝑣UV; = 1の場合 𝑣U, 𝑣UV; ∈ 𝐸かつ𝑑 𝑣UW;, 𝑣UV; = 2の場合 上記以外の場合 ただし Pr(𝑣;<= |𝑣; ) = 𝜋8!,8!"# ∑ 8∈>?@ABCDEFG(8!) 𝜋8!,8 p=q=1ならDeepWalkになる pは再訪性，qは探索の方向を制御するパラメータ
53. node2vecにおけるランダムウォークの遷移確率 𝜋-",-"#$ = . / 1 . 0 𝑣U, 𝑣UV; ∈ 𝐸かつ𝑑 𝑣UW;, 𝑣UV; = 0の場合 𝑣U, 𝑣UV; ∈ 𝐸かつ𝑑 𝑣UW;, 𝑣UV; = 1の場合 𝑣U, 𝑣UV; ∈ 𝐸かつ𝑑 𝑣UW;, 𝑣UV; = 2の場合 ただし Pr(𝑣;<= |𝑣; ) = 𝜋8!,8!"# ∑ 8∈>?@ABCDEFG(8!) 𝜋8!,8 vt vt-1 1ステップ前 にいた場所 現在地ノードと次の移動先候補が隣接しているか 1ステップ前のノードと 移動先候補ノードとの距離 vt+1 vt+1 vt+1
54. p が⼩さい場合 vt vt-1 𝜋-",-"#$ = I 2 1 1 𝑣U, 𝑣UV; ∈ 𝐸かつ𝑑 𝑣UW;, 𝑣UV; = 0の場合 𝑣U, 𝑣UV; ∈ 𝐸かつ𝑑 𝑣UW;, 𝑣UV; = 1の場合 𝑣U, 𝑣UV; ∈ 𝐸かつ𝑑 𝑣UW;, 𝑣UV; = 2の場合 例: p=0.5, q=1のとき 1 𝜋=2 1 1 1つ前のノードへ戻りやすくなる vt+1 vt+1 vt+1
55. p が⼤きい場合 vt vt-1 𝜋-",-"#$ = I 0.5 1 1 𝑣U, 𝑣UV; ∈ 𝐸かつ𝑑 𝑣UW;, 𝑣UV; = 0の場合 𝑣U, 𝑣UV; ∈ 𝐸かつ𝑑 𝑣UW;, 𝑣UV; = 1の場合 𝑣U, 𝑣UV; ∈ 𝐸かつ𝑑 𝑣UW;, 𝑣UV; = 2の場合 例: p=2, q=1のとき 1 𝜋=0.5 1 1 1つ前のノードへ戻りにくくなる vt+1 vt+1 vt+1
56. q が⼩さい場合 vt vt-1 𝜋-",-"#$ = I 1 1 2 𝑣U, 𝑣UV; ∈ 𝐸かつ𝑑 𝑣UW;, 𝑣UV; = 0の場合 𝑣U, 𝑣UV; ∈ 𝐸かつ𝑑 𝑣UW;, 𝑣UV; = 1の場合 𝑣U, 𝑣UV; ∈ 𝐸かつ𝑑 𝑣UW;, 𝑣UV; = 2の場合 例: p=1, q=0.5のとき 1 𝜋=2 1 1つ前のノードから離れるように遷移しやすくなる 2 vt+1 vt+1 vt+1
57. q が⼤きい場合 vt vt-1 𝜋-",-"#$ = I 1 1 0.5 𝑣U, 𝑣UV; ∈ 𝐸かつ𝑑 𝑣UW;, 𝑣UV; = 0の場合 𝑣U, 𝑣UV; ∈ 𝐸かつ𝑑 𝑣UW;, 𝑣UV; = 1の場合 𝑣U, 𝑣UV; ∈ 𝐸かつ𝑑 𝑣UW;, 𝑣UV; = 2の場合 例: p=1, q=2のとき 1 𝜋=0.5 1 1つ前のノードの近くに遷移しやすくなる 0.5 vt+1 vt+1 vt+1
58. node2vecにおけるqの設定 q > 1 幅優先探索的 ランダムウォーク 深さ優先探索的 ランダムウォーク q < 1 DeepWalk 1 2 3 4 1 2 3 4 タスクに応じてパラメータを調整
59. Hands-on タイム 以下のURLにアクセスして， 第14回のクイズQ2を解いてみよう https://graphnote.hontolab.org/ 59
60. node2vec for レ・ミゼラブル⼈物関係グラフ node2vec: Scalable Feature Learning for Networks. A. Grover, J. Leskovec. ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2016. p=1, q=0.5の設定 (深さ優先探索重視) p=1, q=2の設定 (幅優先探索重視) node2vecで得たノード埋め込みに対して K-meansを適⽤した結果 良い表現を得るにはパラメータ設定がシビア…
61. Hands-on タイム 以下のURLにアクセスして， 第14回のクイズQ3-4を解いてみよう https://graphnote.hontolab.org/ 61
62. グラフニューラルネットワーク 3 深層学習 x グラフ
63. node2vecの課題 ノード間で情報が共有されない 「隣接している」という情報を⽤いているが，他のノードが どんな埋め込みベクトルを持っているかは共有されていない 表現学習に使われる情報はグラフ構造のみ ノードは構造情報（隣接ノード & エッジの重み）以外にも、 属性情報ももち得る（例: SNS→ユーザの年齢，性別など） K B A I J D E F C G H SNSの場合 ⼥性, 20代, 愛知県出⾝, 年収yy万円 男性, 30代, 三重県出⾝, 年収xx万円 この情報もノードの 表現学習に使いたいが…
64. 2種類の機械学習プロセス 表現学習 （埋め込み獲得） 推論 決定⽊, SVM K-means, NN, etc.. 主成分分析, BERT Spectral埋め込み node2vec, etc.. 表現学習 （埋め込み獲得） 推論モデル 構築 推論 + 深層学習 グラフ用の深層学習モデルがほしい ⾼品質な 推論モデル 構築
65. 深層学習（DNN; Deep Neural Network）のアーキテクチャ 中間層（隠れ層） … … … …… … … … … … … … …… … …… … …… 固有の役割を持つ様々な部品(層)の組合せで構成 部品を使って構成すると，DNNの構造が分かりやすくなる
66. DNNの主要な部品（層）の例（1/4） 全結合層 (Fully-connected layer) 活性化関数 (Activation function) … … … … ドロップアウト層 (Dropout layer) … … ⼊⼒を線形変換 （全⼊⼒を線形結合） ⼊⼒に⾮線形関数 を適⽤ (ReLU, Softmaxなど) 学習時にランダムに 出⼒ノードを無視 →過学習を防ぐ
67. DNNの主要な部品（層）の例（2/4） 畳み込み層 (Convolution layer) テンソルにフィルタをかけて フィルタ領域の情報を圧縮し、 別のテンソルを得る フィルタの値とフィルタが 重なる箇所の値を掛け、 総和を和をとる 1 1 1 0 0 1 0 1 1 0 1 0 1 1 1 0 テンソル（⾏列の⼀般化） 3 2 2 1 2 1 2 2 1 1 1 0 1 フィルタ 適⽤後のテンソル フィルタの重みはデータから学習される
68. 3 2 2 5 1 2 1 3 2 2 1 4 1 7 2 2 DNNの主要な部品（層）の例（3/4） プーリング層 (Pooling layer) あらかじめ定めた関数を使い テンソルの部分領域情報を 圧縮し、別のテンソルを得る テンソル（⾏列の⼀般化） プーリング関数 適⽤後テンソル 最⼤値 どれ? 3 5 7 4 最⼤値プーリング以外にも 平均プーリングなどがある
69. DNNの主要な部品（層）の例（4/4） 平坦化関数(Flatten function) N階テンソルを1階テンソル（ベクトル）に変換する 3階テンソル (M×Nの⾏列が3枚) 1階テンソル (M×N×3次元のベクトル) flatten
70. 画像を分析する深層学習アーキテクチャの例 = 畳み込み +活性化 Pooling +活性化 平坦化 … … … …… … … … … … … … …… 全 結 合 層 活性化関数 （=Softmax） ひまわり RGB⾊空間上の 3枚の⾏列 （3階テンソル）
71. 表現学習(埋め込み) 画像を分析する深層学習アーキテクチャの例 畳 み 込 み 層 活 性 化 関 数 プ ｜ リ ン グ 層 活 性 化 関 数 平 坦 化 関 数 全 結 合 層 活 性 化 関 数 … 推 論 結 果 推論 グラフにも深層学習を持ち込めないか??
72. グラフに対しても深層学習モデルが使えれば 画像出典1: https://commons.wikimedia.org/ … 1 2 3 4 5 6 7 8 9 10 11 12 13 1 2 3 13 埋め 込み ノードの埋め込みベクトル 圧縮 … グラフ 埋め込みベクトル 予測 精神安定効果 アリ グラフ化 深層学習がすべて担当
73. グラフ畳み込み（GCN; Graph Convolutional Network） 隣接ノードの情報を集約しノード埋め込みを得る方法 - ノードの属性情報(例: 性別)も活⽤可能 - 教師あり学習を通じて，埋め込みとノード集約時の重みを学習 更新 k層⽬通過時 k+1層⽬通過時 グラフ 畳み込み 1 2 3 4 5 6 0 1 2 3 4 5 6 0 × w1,0 × w4,0 × w5,0 × w6,0 × w0,0
74. 画像畳み込みとグラフ畳み込みの⽐較 画像出典: グラフニューラルネットワーク（機械学習プロフェッショナルシリーズ） 画像畳み込み グラフ畳み込み k層 k+1層
75. グラフ畳み込み（2/2） 隣接ノードの情報を集約しノード埋め込みを得る方法 - ノードの属性情報(例: 性別)も活⽤可能 - 教師あり学習を通じて，埋め込みとノード集約時の重みを学習 更新 k+1層⽬通過時 1 2 3 4 5 6 0 × w1,0 × w4,0 × w5,0 × w6,0 × w0,0 𝜎( 0 %∈'%()*+ , 1 𝑳%,, 𝑤%,, ) 𝒉% ) + 1 𝑳,,, 𝑤,,, ) 𝒉, ())) 𝒉X YV; = k層⽬通過後のノードの 埋め込みベクトル (学習で求める)
76. グラフ畳み込み（2/2） 隣接ノードの情報を集約しノード埋め込みを得る方法 - ノードの属性情報(例: 性別)も活⽤可能 - 教師あり学習を通じて，埋め込みとノード集約時の重みを学習 更新 k+1層⽬通過時 1 2 3 4 5 6 0 × w1,0 × w4,0 × w5,0 × w6,0 × w0,0 𝜎( 0 %∈'%()*+ , 1 𝑳%,, 𝑤%,, ) 𝒉% ) + 1 𝑳,,, 𝑤,,, ) 𝒉, ())) 𝒉X YV; = k+1層⽬で集約演算時の 重みパラメータ (学習で求める)
77. グラフ畳み込み（2/2） 隣接ノードの情報を集約しノード埋め込みを得る方法 - ノードの属性情報(例: 性別)も活⽤可能 - 教師あり学習を通じて，埋め込みとノード集約時の重みを学習 更新 k+1層⽬通過時 1 2 3 4 5 6 0 × w1,0 × w4,0 × w5,0 × w6,0 × w0,0 𝜎( 0 %∈'%()*+ , 1 𝑳%,, 𝑤%,, ) 𝒉% ) + 1 𝑳,,, 𝑤,,, ) 𝒉, ())) 𝒉X YV; = 正規化グラフラプラシアンの値 （隣接⾏列から得られる定数）
78. グラフ畳み込み（2/2） 隣接ノードの情報を集約しノード埋め込みを得る方法 - ノードの属性情報(例: 性別)も活⽤可能 - 教師あり学習を通じて，埋め込みとノード集約時の重みを学習 更新 k+1層⽬通過時 1 2 3 4 5 6 0 × w1,0 × w4,0 × w5,0 × w6,0 × w0,0 𝜎( 0 %∈'%()*+ , 1 𝑳%,, 𝑤%,, ) 𝒉% ) + 1 𝑳,,, 𝑤,,, ) 𝒉, ())) 𝒉X YV; = 活性化関数 for ⾮線形化 (e.g. ReLU)
79. グラフ畳み込み（2/2） 隣接ノードの情報を集約しノード埋め込みを得る方法 - ノードの属性情報(例: 性別)も活⽤可能 - 教師あり学習を通じて，埋め込みとノード集約時の重みを学習 更新 k+1層⽬通過時 1 2 3 4 5 6 0 × w1,0 × w4,0 × w5,0 × w6,0 × w0,0 𝑯 YV; = 𝜎(L 𝑫W ; ZL 𝑨L 𝑫W ; Z𝑯(Y)𝑾(Y)) 𝜎( 0 %∈'%()*+ , 1 𝑳%,, 𝑤%,, ) 𝒉% ) + 1 𝑳,,, 𝑤,,, ) 𝒉, ())) 𝒉X YV; = 全ノードの演算について ⾏列で書く
80. 表現学習(埋め込み) グラフ深層学習アーキテクチャの例 グ ラ フ 畳 み 込 み 層 活 性 化 関 数 グ ラ フ 畳 み 込 み 層 活 性 化 関 数 平 坦 化 関 数 全 結 合 層 活 性 化 関 数 … 推 論 結 果 推論
81. グラフ深層学習アーキテクチャの例 グ ラ フ 畳 み 込 み 層 活 性 化 関 数 平 坦 化 関 数 全 結 合 層 活 性 化 関 数 … 推 論 結 果 グ ラ フ 畳 み 込 み 層 活 性 化 関 数 表現学習(埋め込み) グラフ畳み込み 1回⽬ 1回目の畳み込みで隣接ノードの情報を取り込んでいる 𝑯 = = 𝜎(9 𝑫P = Q9 𝑨9 𝑫P = Q𝑯(R)𝑾(R))
82. グラフ深層学習アーキテクチャの例 グ ラ フ 畳 み 込 み 層 活 性 化 関 数 平 坦 化 関 数 全 結 合 層 活 性 化 関 数 … 推 論 結 果 グ ラ フ 畳 み 込 み 層 活 性 化 関 数 表現学習(埋め込み) グラフ畳み込み 1回⽬ 𝑯 = = 𝜎(9 𝑫P = Q9 𝑨9 𝑫P = Q𝑿𝑾(R)) H(0)の代わりにノードの属性ベクトルを指定すると モデルにノード属性を取り込むことができる
83. グラフ深層学習アーキテクチャの例 平 坦 化 関 数 全 結 合 層 活 性 化 関 数 … 推 論 結 果 グ ラ フ 畳 み 込 み 層 活 性 化 関 数 グラフ畳み込み 2回⽬ グ ラ フ 畳 み 込 み 層 活 性 化 関 数 2回目の畳み込みでは間接的に2ホップ先のノードを取り込んでいる 𝑯 Q = 𝜎(9 𝑫P = Q9 𝑨9 𝑫P = Q𝑯(=)𝑾(=))
84. グラフ深層学習アーキテクチャの例 平 坦 化 関 数 全 結 合 層 活 性 化 関 数 推 論 結 果 グ ラ フ 畳 み 込 み 層 活 性 化 関 数 2回の グラフ畳み込み グ ラ フ 畳 み 込 み 層 活 性 化 関 数 グラフ畳み込みは2層（回）が最高性能を示すことが多い
85. グラフ深層学習の進展 グラフ特徴を捉える様々なアーキテクチャの開発 - 注意機構や再帰ユニットの取り⼊れ - ノードやエッジに複数の種類がある異種混合グラフへの拡張 グラフニューラルネットワークの高速化 - 計算速度の向上に特化したアーキテクチャの開発 - 集約対象とする近傍ノードのサンプリング⽅法の⼯夫 過平滑化現象への対策 グラフ深層学習は層を深くすると、すべての頂点の特徴が ほぼ同じ値になってしまう現象が起きる
86. 授業計画 86 回 トピック 9 グラフデータ 10 グラフ構造の諸指標 11 ノードの中心性 12 コミュニティ発見 13 ウェブとグラフ 14 グラフ埋め込み 15 総合演習 – 社会ネットワーク分析