Share
Embed
データマイニング - グラフ埋め込み入門
1. スペクトラルクラスタリング
2. ランダムウォーク × 埋め込み
3. グラフニューラルネットワーク
Y. Yamamoto PRO
July 18, 2025
Transcript
86 slides
-
グラフ埋め込み ⼭本 祐輔 名古屋市⽴⼤学 データサイエンス研究科 [email protected] 第14回 データマイニング (グラフ分析入門) ⼭本祐輔
クリエイティブコモンズライセンス (CC BY-NC-SA 4.0) -
典型的なグラフ分析のタスク(2/2) ノード分類 ノード間の関係性予測 つながる? ⻘, 緑, 黒? 友達 友達 友達
先輩-後輩 何関係? エッジ分類 これは何のグラフ? グラフ分類 -
タスクに応じたグラフ分析⼿法の例 コミュニティ発⾒ ノード中⼼性評価 分析 近接中⼼性, 媒介中⼼性, 固有ベクトル中⼼性, PageRank, … 分析
連結成分抽出, Girvan-Newman法, リンクコミュニティ法, … -
タスク再考 コミュニティ発⾒ ノード分類 ⻘, 緑, 黒? ノードのクラスタリング (教師なし学習) ノードの分類問題 (教師あり学習)
汎用的な機械学習手法が使えないのか? -
グラフ分析 と 汎⽤機械学習 グラフ ベクトル 汎⽤機械学習⼿法 適⽤ グラフ分析⼿法 適⽤ 変換
変換 𝑥!,! 𝑥!,# … 𝑥!,!$ 𝑥#,! 𝑥#,# … 𝑥#,!$ ⋮ ⋮ ⋱ ⋮ 𝑥!$,! 𝑥!$,# … 𝑥!$,!$ グラフ-ベクトル間で変換できれば,それぞれの手法が使える!! -
ベクトル化ができれば(1/2) フォローを おすすめ? Type equation here. 𝑣!" = 3.14 −1.59
⋮ 2.65 𝑣#$ = 2.71 −8.28 ⋮ 1.82 -
ベクトル化ができれば(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 から にエッジが張られている から にはエッジが張られていない -
ベクトル化さえできれば,汎⽤機械学習でリンク予測が可能 # 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] # リンクが張れると予測 … -
グラフ埋め込み (Graph Embedding) A C N次元の埋め込み空間 グラフ B 𝒗3 𝒗4
𝒗5 埋め込み グラフあるいはその要素を低次元の密ベクトルに変換したもの グラフ埋め込み表現 表現学習 データから質の良い埋め込み表現を獲得するためのタスク 良い埋め込み表現は、埋め込み空間上で似たノード同士を近くに配置する -
グラフをベクトル化する超単純な⽅法 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の 隣接関係 -
グラフをベクトル化する超単純な⽅法 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 類似度ゼロ (遠く離れているので妥当) -
グラフをベクトル化する超単純な⽅法 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 類似度⾼い (つながりが似ているので妥当) -
グラフをベクトル化する超単純な⽅法 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 類似度ゼロ (隣り合っているのに!?) 何が問題なのか? -
隣接⾏列の⾏をノードのベクトルと⾒なす問題点 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 行列のスパース性 隣接⾏列の⼤部分は値がゼロ(世の中の⼤抵のグラフはスパース(疎)) グラフの特徴の捉え方が不十分 ノードの構造的特徴は隣接ノードだけでは決まらない (グラフにおける相対的な位置づけを⾒ていない) どうすれば密で特徴を捉えた良質な埋め込みが得られるか? スパース!! スパース!! -
スペクトラルクラスタリング(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 -
スペクトラルクラスタリングの問題設定 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 理想的な割り当ての例 隣接するノードは 差が⼩さい 隣接しないノードは 差が⼤きい -
スペクトラルクラスタリングの問題設定 0 2 3 4 1 5 10 8 7
6 9 各ノードに何らかの数値を割り当てたいが、 隣接しているノードにはできる限り近い値を割り当てる 𝐿(𝒙) = 7 %,'∈)! 𝐴%,' |𝑥% − 𝑥' | 問題定義 ノードiとjの 割当値の差を⾒る -
スペクトラルクラスタリングの問題設定 0 2 3 4 1 5 10 8 7
6 9 各ノードに何らかの数値を割り当てたいが、 隣接しているノードにはできる限り近い値を割り当てる 𝐿(𝒙) = 7 %,'∈)! 𝐴%,' |𝑥% − 𝑥' | 問題定義 ただし,iとjが隣接 している時のみ注⽬する (Ai,j は隣接⾏列Aの(i,j)要素の値 で隣接していたら1,隣接して いなかったら0となる) -
スペクトラルクラスタリングの問題設定 0 2 3 4 1 5 10 8 7
6 9 各ノードに何らかの数値を割り当てたいが、 隣接しているノードにはできる限り近い値を割り当てる 𝐿(𝒙) = 7 %,'∈)! 𝐴%,' 𝑥% − 𝑥' * 問題定義 絶対値を⾒ても ⼆乗を⾒ても同じ -
スペクトラルクラスタリングの問題設定 0 2 3 4 1 5 10 8 7
6 9 各ノードに何らかの数値を割り当てたいが、 隣接しているノードにはできる限り近い値を割り当てる 𝐌𝐢𝐧𝐢𝐦𝐢𝐳𝐞 𝐿(𝒙) = 7 %,'∈)! 𝐴%,' 𝑥% − 𝑥' * 問題定義 s. t. 𝑥# % + 𝑥% % + ⋯ + 𝑥& % = 𝒙 % = 1 全ノードの組み合わせ について調べる -
スペクトラルクラスタリングの問題設定 0 2 3 4 1 5 10 8 7
6 9 各ノードに何らかの数値を割り当てたいが、 隣接しているノードにはできる限り近い値を割り当てる 𝐌𝐢𝐧𝐢𝐦𝐢𝐳𝐞 𝐿(𝒙) = 7 %,'∈)! 𝐴%,' 𝑥% − 𝑥' * 問題定義 s. t. 𝑥# % + 𝑥% % + ⋯ + 𝑥& % = 𝒙 % = 1 値が無限に⼤きくならないよう 制約を与える -
スペクトラルクラスタリングの問題設定 0 2 3 4 1 5 10 8 7
6 9 各ノードに何らかの数値を割り当てたいが、 隣接しているノードにはできる限り近い値を割り当てる 𝐌𝐢𝐧𝐢𝐦𝐢𝐳𝐞 𝐿(𝒙) = 7 %,'∈)! 𝐴%,' 𝑥% − 𝑥' * 問題定義 s. t. 𝑥# % + 𝑥% % + ⋯ + 𝑥& % = 𝒙 % = 1 最小化問題に帰着させる -
式変形 (1/2) 𝐿 𝒙 = 7 %,'∈)! 𝐴%,' 𝑥% −
𝑥' * = 7 %,'∈)! 𝐴%,' (𝑥% * − 2𝑥% 𝑥' + 𝑥' *) = 7 %,'∈)! 𝐴%,' (𝑥% * + 𝑥' *) − 2 7 %,'∈)! 𝐴%,' 𝑥% 𝑥' 𝐴>? = 𝐴?> 無向グラフの場合, Aは対称⾏列なので @ %,&∈(! 𝐴%,& 𝑥% # = @ %,&∈(! 𝐴%,& 𝑥& # このとき -
式変形 (1/2) 𝐿 𝒙 = 7 %,'∈)! 𝐴%,' 𝑥% −
𝑥' * = 7 %,'∈)! 𝐴%,' (𝑥% * − 2𝑥% 𝑥' + 𝑥' *) = 7 %,'∈)! 𝐴%,' (𝑥% * + 𝑥' *) − 2 7 %,'∈)! 𝐴%,' 𝑥% 𝑥' = 7 %,'∈)! 𝐴%,' (2𝑥% *) − 2 7 %,'∈)! 𝐴%,' 𝑥% 𝑥' = 2 7 %,'∈)! 𝐴%,' 𝑥% * − 7 %,'∈)! 𝐴%,' 𝑥% 𝑥' 先にjに関する和を取ると 6 '∈)! 𝐴*,' = 6 '∈)! 𝐷*,* (D は次数⾏列) 6 *,'∈)! 𝐴*,' 𝑥* % = 6 *∈)! 𝐷*,* 𝑥* % -
式変形 (2/2) 𝐿 𝒙 = 2 7 %,'∈)! 𝐴%,' 𝑥%
* − 7 %,'∈)! 𝐴%,' 𝑥% 𝑥' = 2 7 %,'∈)! 𝐷%,% 𝑥% * − 7 %,'∈)! 𝐴%,' 𝑥% 𝑥' = 2 𝒙/𝑫𝒙 − 𝒙/𝑨𝒙 = 2𝒙!𝓛𝒙 ℒ = 𝐷 − 𝐴 : 次数⾏列 : 隣接⾏列 : グラフラプラシアン ただし, ℒ 𝐷 𝐴 -
スペクトルクラスタリングにおける最適化問題 𝐌𝐢𝐧𝐢𝐦𝐢𝐳𝐞 𝐿(𝒙) = 7 %,'∈)! 𝐴%,' 𝑥% − 𝑥'
* s. t. 𝑥# % + 𝑥% % + ⋯ + 𝑥& % = 𝒙 % = 1 = 2𝒙+𝓛𝒙 ラグランジュの未定乗数法 𝜕 𝜕𝒙 2𝒙+𝓛𝒙 − 𝜆′ 𝒙𝑻𝒙 − 1 = 2𝓛𝒙 − 2𝜆𝒙 = 0 となる x を求める問題になる. 𝓛𝒙 = 𝜆𝒙 これは となる x を求める問題,つまり 𝓛の固有値問題に帰着される -
グラフラプラシアンの固有値と固有ベクトル 𝓛𝒙 = 𝜆𝒙 2𝒙!𝓛𝒙 = 2𝒙!𝜆𝒙 = 2𝜆𝒙!𝒙 =
2𝜆 2𝒙!𝓛𝒙 = 𝐿 𝒙 = 2𝜆 両辺に左から2xTをかける 制約条件 |x|2 = xTx =1を思い出す そもそも我々はL(x)= 2𝒙)𝓛𝒙 の最⼩化問題を解いていた 固有値 λ は目的関数の最小値 (の候補)、 固有ベクトル x はノードに割当値(の候補)を示している -
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番⽬に⼩さい固有値に 対応する固有ベクトル ⼤きい固有値に対応 する固有ベクトルは無視 -
単語埋め込み (Word Embedding) 単語の潜在的な意味を捉えるために、 単語を低次元の密ベクトルに変換する技術 - 単語の意味の類似性や単語間の関係性が演算可能に - 単語埋め込みは機械による⽂章理解のための基礎 (e.g.
Transformer) 類似性の演算 ⼥ 男 冷蔵庫 近い 遠い 𝑑𝑖𝑠𝑡 𝑣男, 𝑣⼥ < 𝑑𝑖𝑠𝑡(𝑣男, 𝑣冷蔵庫) 関係性の演算 ⼥ 男 王 𝑣⼥ − 𝑣男 + 𝑣王 = 𝑣⼥王 ⼥王 ベクトル演算 どうやって意味ベクトルを獲得するのか? -
Harrisの分布仮説 単語の意味は、その周囲に現れる単語によって決まる 仮説 海 で 釣った 魚 を 刺⾝ にして
⾷べる ⽔族館 は 海獣 や 魚 との 距離 が 近い アジ は 回遊 魚 で ⽇本 各地 で 釣れる Harris, Z. (1954). Distributional structure. Word, 10(23): 146-162. -
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モデル) -
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. 海 で 釣った ? を 刺⾝ にして ⾷べる アジ は 回遊 ? で ⽇本 各地 で 釣れる 海 で 釣った ⿂ を ? にして ⾷べる … 大量の文書を使って 埋め込みベクトルと単語予測の学習を行う -
Word2Vec × グラフ埋め込み 海 → 釣った → ⿂ → 刺⾝
単語の系列 Word2Vec 単語の 埋め込み表現 𝑣S ⿂ = (3.5, −2.7, … , 6.1) グラフ 変換!? ノードの系列 Word2Vec ノードの 埋め込み表現 𝑣T • = (3.5, −2.7, … , 6.1) どうやってグラフをノード系列に変換するか? -
グラフ上のランダムウォーク 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 -
ランダムウォークによるノード系列の⽣成 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 … ノード系列 グラフ 任意の出発ノードからランダムウォークを繰り返すことで 任意の長さのノード系列を無限に生成 -
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を適⽤ -
グラフ構造から⾒える(⾒たい)ノードの傾向 ホモフィリー 俯瞰したときに、類似の コミュニティに属している? 構造的同値性 他のノード群と 接続パターンが類似している? ノードの⼤域的関係性 に注⽬する必要アリ ノードの局所的関係性
に注⽬する必要アリ タスクに応じてどちらを重視するか制御したい -
深さ優先探索と幅優先探索 深さ優先探索 (DFS) 幅優先探索 (BFS) 1 2 3 4 1
2 3 4 ⼤域的関係性を掘り下げる 系列をリストアップ 局所的関係性を掘り下げる 系列をリストアップ ホモフィリーを 捉えたいタスク向き 構造的同値性を 捉えたいタスク向き -
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を設定 -
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 -
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は探索の方向を制御するパラメータ -
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 -
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 -
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 -
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 -
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 -
node2vecにおけるqの設定 q > 1 幅優先探索的 ランダムウォーク 深さ優先探索的 ランダムウォーク q <
1 DeepWalk 1 2 3 4 1 2 3 4 タスクに応じてパラメータを調整 -
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を適⽤した結果 良い表現を得るにはパラメータ設定がシビア… -
node2vecの課題 ノード間で情報が共有されない 「隣接している」という情報を⽤いているが,他のノードが どんな埋め込みベクトルを持っているかは共有されていない 表現学習に使われる情報はグラフ構造のみ ノードは構造情報(隣接ノード & エッジの重み)以外にも、 属性情報ももち得る(例: SNS→ユーザの年齢,性別など)
K B A I J D E F C G H SNSの場合 ⼥性, 20代, 愛知県出⾝, 年収yy万円 男性, 30代, 三重県出⾝, 年収xx万円 この情報もノードの 表現学習に使いたいが… -
2種類の機械学習プロセス 表現学習 (埋め込み獲得) 推論 決定⽊, SVM K-means, NN, etc.. 主成分分析,
BERT Spectral埋め込み node2vec, etc.. 表現学習 (埋め込み獲得) 推論モデル 構築 推論 + 深層学習 グラフ用の深層学習モデルがほしい ⾼品質な 推論モデル 構築 -
深層学習(DNN; Deep Neural Network)のアーキテクチャ 中間層(隠れ層) … … … …… …
… … … … … … …… … …… … …… 固有の役割を持つ様々な部品(層)の組合せで構成 部品を使って構成すると,DNNの構造が分かりやすくなる -
DNNの主要な部品(層)の例(1/4) 全結合層 (Fully-connected layer) 活性化関数 (Activation function) … … …
… ドロップアウト層 (Dropout layer) … … ⼊⼒を線形変換 (全⼊⼒を線形結合) ⼊⼒に⾮線形関数 を適⽤ (ReLU, Softmaxなど) 学習時にランダムに 出⼒ノードを無視 →過学習を防ぐ -
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 フィルタ 適⽤後のテンソル フィルタの重みはデータから学習される -
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 最⼤値プーリング以外にも 平均プーリングなどがある -
画像を分析する深層学習アーキテクチャの例 = 畳み込み +活性化 Pooling +活性化 平坦化 … … …
…… … … … … … … … …… 全 結 合 層 活性化関数 (=Softmax) ひまわり RGB⾊空間上の 3枚の⾏列 (3階テンソル) -
表現学習(埋め込み) 画像を分析する深層学習アーキテクチャの例 畳 み 込 み 層 活 性 化
関 数 プ | リ ン グ 層 活 性 化 関 数 平 坦 化 関 数 全 結 合 層 活 性 化 関 数 … 推 論 結 果 推論 グラフにも深層学習を持ち込めないか?? -
グラフに対しても深層学習モデルが使えれば 画像出典1: https://commons.wikimedia.org/ … 1 2 3 4 5 6
7 8 9 10 11 12 13 1 2 3 13 埋め 込み ノードの埋め込みベクトル 圧縮 … グラフ 埋め込みベクトル 予測 精神安定効果 アリ グラフ化 深層学習がすべて担当 -
グラフ畳み込み(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 -
グラフ畳み込み(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層⽬通過後のノードの 埋め込みベクトル (学習で求める) -
グラフ畳み込み(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層⽬で集約演算時の 重みパラメータ (学習で求める) -
グラフ畳み込み(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; = 正規化グラフラプラシアンの値 (隣接⾏列から得られる定数) -
グラフ畳み込み(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) -
グラフ畳み込み(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; = 全ノードの演算について ⾏列で書く -
表現学習(埋め込み) グラフ深層学習アーキテクチャの例 グ ラ フ 畳 み 込 み 層
活 性 化 関 数 グ ラ フ 畳 み 込 み 層 活 性 化 関 数 平 坦 化 関 数 全 結 合 層 活 性 化 関 数 … 推 論 結 果 推論 -
グラフ深層学習アーキテクチャの例 グ ラ フ 畳 み 込 み 層 活
性 化 関 数 平 坦 化 関 数 全 結 合 層 活 性 化 関 数 … 推 論 結 果 グ ラ フ 畳 み 込 み 層 活 性 化 関 数 表現学習(埋め込み) グラフ畳み込み 1回⽬ 1回目の畳み込みで隣接ノードの情報を取り込んでいる 𝑯 = = 𝜎(9 𝑫P = Q9 𝑨9 𝑫P = Q𝑯(R)𝑾(R)) -
グラフ深層学習アーキテクチャの例 グ ラ フ 畳 み 込 み 層 活
性 化 関 数 平 坦 化 関 数 全 結 合 層 活 性 化 関 数 … 推 論 結 果 グ ラ フ 畳 み 込 み 層 活 性 化 関 数 表現学習(埋め込み) グラフ畳み込み 1回⽬ 𝑯 = = 𝜎(9 𝑫P = Q9 𝑨9 𝑫P = Q𝑿𝑾(R)) H(0)の代わりにノードの属性ベクトルを指定すると モデルにノード属性を取り込むことができる -
グラフ深層学習アーキテクチャの例 平 坦 化 関 数 全 結 合 層
活 性 化 関 数 … 推 論 結 果 グ ラ フ 畳 み 込 み 層 活 性 化 関 数 グラフ畳み込み 2回⽬ グ ラ フ 畳 み 込 み 層 活 性 化 関 数 2回目の畳み込みでは間接的に2ホップ先のノードを取り込んでいる 𝑯 Q = 𝜎(9 𝑫P = Q9 𝑨9 𝑫P = Q𝑯(=)𝑾(=)) -
グラフ深層学習アーキテクチャの例 平 坦 化 関 数 全 結 合 層
活 性 化 関 数 推 論 結 果 グ ラ フ 畳 み 込 み 層 活 性 化 関 数 2回の グラフ畳み込み グ ラ フ 畳 み 込 み 層 活 性 化 関 数 グラフ畳み込みは2層(回)が最高性能を示すことが多い -
グラフ深層学習の進展 グラフ特徴を捉える様々なアーキテクチャの開発 - 注意機構や再帰ユニットの取り⼊れ - ノードやエッジに複数の種類がある異種混合グラフへの拡張 グラフニューラルネットワークの高速化 - 計算速度の向上に特化したアーキテクチャの開発 -
集約対象とする近傍ノードのサンプリング⽅法の⼯夫 過平滑化現象への対策 グラフ深層学習は層を深くすると、すべての頂点の特徴が ほぼ同じ値になってしまう現象が起きる -
授業計画 86 回 トピック 9 グラフデータ 10 グラフ構造の諸指標 11 ノードの中心性
12 コミュニティ発見 13 ウェブとグラフ 14 グラフ埋め込み 15 総合演習 – 社会ネットワーク分析