【グラフニューラルネットワーク】2.3

グラフニューラルネットワーク第２章３節 古典的なグラフ機械学習⼿法 京都⼤学医学研究科 M1 ⼩林侑⼤ 0

2.古典的なグラフ機械学習⼿法 ⽬次 1. ラベル伝搬法ー転導的頂点⼆値分類問題 2. ⾏列分解 3. Deep Walk 1

2.3 古典的なグラフ機械学習⼿法

2.3.1ラベル伝搬法

転導的頂点⼆値分類問題
𝑉# :ラベル既知頂点

𝑉! :ラベル未知頂点

0

1 𝑤

(

?

𝑤'

𝑤$

0

?
𝑤 -

予測

%

𝑤&

?

0 or 1

•

重みは類似度を表す。

•

⽬的は類似度をもとに頂点のラベル
るを予測すること。
→例えば、𝑤! が⼤きい場合、
?" を 0と予測できれば良い

⼊⼒︓重み付きグラフ ( 𝐺 = 𝑉, 𝐸, 𝑤 )
出⼒︓教師ラベルの付いていない頂点 𝑉!
について、ラベルの推定値 )
𝑦" (0か1) を求める。

2

2.3 古典的なグラフ機械学習⼿法 2.3.1 ラベル伝搬法 解くべき最適化問題 求めたい 0 1𝑊 𝑊$% $) ? 𝑊$( 0 𝑊$& ? • (𝒇 ∈ ℝ# ) は頂点のラベルの推定値を表すベクトル • 予測値は、𝒇𝒗 ≥ 0.5であれば , 𝑦% = 1 と し、𝒇𝒗 < 0.5であれば , 𝑦% = 0 とする。 • 類似度が⼤きい頂点が重要視される • 類似度が⼤きい頂点同⼠は同じラベル になる。 𝑊$' ? 3

2.3 古典的なグラフ機械学習⼿法 2.3.1 ラベル伝搬法 ラベル伝搬法の解 ⽬的関数の最⼩値を求めれば良いので、⽬的関数を 𝑓& について偏微分して 未知 既知 頂点のラベルの推定値で未知のものの集合𝑓' を 、 既知のものの集合 𝑓( だけで表せた︕ 勾配の式を0で解くと最終的に式(2.28)のように解 ける。 4

2.3 古典的なグラフ機械学習⼿法 2.3.1 ラベル伝搬法 ランダムウォークを⽤いた解釈 ラベル伝搬法の解𝑓% は頂点𝑣から初めて訪れた教師 付きラベルが１である確率𝑞% ∈ 0,1 と⼀致する。 0 𝑣 𝑊%) deg 𝑣 𝑢 • 類似度が⼤きい辺ほど⾼い確 率で渡っていく。 • deg 𝑣 は頂点(𝑣) に接続しているエッジの重みの合計 • ラベル伝搬法は近くにある頂 点同⼠が同じラベルになるよ うに分類される。 • 式(2.30)と式(2.25)は等価 𝑞と𝑓も⼀致。 0 𝑣 𝑞" 0 1 1 5

2.3 古典的なグラフ機械学習⼿法 2.3.2 ⾏列分解 教師なし頂点表現学習問題 • 埋め込み(embedding)︓デ ータの情報を低次元のベクト ルとして表現したもの • 表現学習︓埋め込みを学習す る • 重み付きグラフの接続⾏列 𝐵&* は頂点の埋め込みになっ ている。 頂点の埋め込み Z" ∈ ℝ, 𝑣 𝑢 頂点の埋め込み Z- ∈ ℝ, 𝑍-. Z" → 辺uvの構造の情報 𝑍". Z" → 頂点vの構造の情報 みたいに表せたら嬉しい。 ⼊⼒︓重み付きグラフ ( 𝐺 = 𝑉, 𝐸, 𝑤 ) 出⼒︓グラフ構造を考慮した頂点の埋め込みZ ∈ ℝ*×, 6

2.3 古典的なグラフ機械学習⼿法 2.3.2 ⾏列分解 教師なし頂点表現学習問題 解くべき最適化問題 • この問題ではスペクトル分 解と特異値分解どちらでも 同じ解となる • 分かりやすそうなサイト グラフの構造の情報と頂点の埋め込みの積を近づけていく このような問題は⾏列分解により解くことができる。 • ・スペクトル分解→固有値を利⽤した分解 ・特異値分解→特異値を利⽤した分解 この問題の解↓ • スペクトル分解 https://qiita.com/jamojisan/ite ms/b8f7a7e9b44fc3e2e41c 特異値分解︓ https://qiita.com/kidaufo/items/ 0f3da4ca4e19dc0e987e 7

• https://qiita.com/jamojisan/items/b8f7a7e9b44fc3e2e41c
• https://qiita.com/kidaufo/items/0f3da4ca4e19dc0e987e

2.3 古典的なグラフ機械学習⼿法 2.3.2 ⾏列分解 トピック推定 ⽂書と単語の関係性を埋め込む 解くべき最適化問題 ⼊⼒： 単語の集合 {𝑤$ , 𝑤% , … , 𝑤/ } 出⼒︓各⽂書 𝑡0 のトピックの割当変量 𝑈0 ∈ ℝ, (𝑖 ∈ 𝑇 ) 各単語 𝑤0 のトピックの割当変量 𝑉0 ∈ ℝ, (𝑖 ∈ 𝑊 ) 𝑋& ∈ ℝ+ は𝑏𝑎𝑔 𝑜𝑓 𝑤𝑜𝑟𝑑𝑠といい、𝑋&* ∈ ℝは ⽂書𝑡& 中に単語𝑤* が出現する回数を表す。 この最適化問題は特異値分解で解くことができ、この ような解析⼿法を潜在意味解析という。 8

2.3 古典的なグラフ機械学習⼿法 2.3.2 ⾏列分解 映画推薦問題 解くべき最適化問題 ⼊⼒： ユーザーの映画の評価履歴 {(𝑢0 , 𝑣1 , 𝑟01 )} 出⼒︓各ユーザーに対するおすすめの映画 ユーザーと映画の埋め込みを計算した後は、各ユーザ ー𝑢& が未評価の映画𝑣* につけるであろう評価値を , 𝑟&* = 𝑈&, 𝑉& として推定することができる。 この評価値が最も⾼い未評価の映画をユーザー 𝑢& に推 薦する。 このように傾向の似た他のユーザーの消費した品⽬に 基づいて推薦を⾏う技法を協調フィルタリングという 9

2.3 古典的なグラフ機械学習⼿法 2.3.3 Deep Walk 教師なし頂点表現学習問題 A ⼊⼒︓重み付きグラフ ( 𝐺 = 𝑉, 𝐸, 𝑤 ) 出⼒︓グラフ構造を考慮した頂点の埋め込みZ ∈ ℝ*×, A B B C C D 頂点𝑢の周辺という条件のもとでの頂点𝑣の出現確率を 𝑝∗(𝑣|𝑢)とあらわす。 F G F G E E ランダムウォーク： モデルのもとで、頂点𝑣が頂点𝑢の周囲い登場する確率を D A 私 C の F 名前 E は Aの周辺 と定義する。うまく学習できると、頂点𝑣と頂点𝑢の類似 度がわかる︕ 10

2.3 古典的なグラフ機械学習⼿法 2.3.3 Deep Walk 教師なし頂点表現学習問題 最⼤化する⽬的関数 真の頂点𝑢周辺の頂点𝑣の出現確率と予測した頂点𝑢周辺の頂点𝑣の出現確率を近づけていく • KLはカルバック・ライブラ ー情報量 (Kullback-Leibler divegrence) であり、⾮負 で2つの確率分布が等しいか つその時のみ０となる。簡 単⾔えば、2つの確率分布の 距離のような意味を持つ。 最適化の⼿法は確率的勾配向上法を⽤いて⾏う このままでは、(2.57)の分⺟の計算が⼤変なので、そ れを避けるための⽅法としてネガティブサンプリング が紹介されていた。 11