【グラフニューラルネットワーク】5.1~5.4

グラフニューラルネットワーク 5.グラフニューラルネットワークの高速化 (5.1-5.4) 野村隆晃 0

計算量 グラフニューラルネットワークの計算量 𝑂(𝑚𝑑𝐿 + 𝑛𝑑2 𝐿) メッセージ伝達 ● ● ● ● 中間表現の変換 𝑚:辺の数 𝑑:中間表現𝒉の次元数 𝐿:階層数 𝑛:頂点数 グラフの大きさに対して線形時間で終わる →グラフが大きいと、線形時間ですら高速とは言えない… 1

高速化が難しい理由 第𝐿層のニューラルネットワークに関して、𝒩𝐿 (𝑣)が必要である。 𝐿を大きくすると近傍点集合の点の個数がめっちゃでかくなりがち 具体例) 地球上のどのような人(70億人)にも5人の知り合いで到達 可能 2

5.2 高速なアーキテクチャ 単純グラフ畳み込み ● ● ● 𝑍 = 𝐴መ 𝐿 𝑋𝑊 𝐴መ = 𝐷−0.5 𝐴𝐷 −0,5 : 隣接行列に自己ループを加えて、次数行列で 正規化したもの 𝑋 ′ = 𝐴መ 𝐿 Xは一回計算すれば使いまわせるので、𝑍 = 𝑋 ′ 𝑊 線形で表現力が足りない場合は、グラフフィルタニューラルネ ットワーク𝑍𝑣 = 𝑀𝐿𝑃𝜃 (𝑋𝑣′ ) (復習:𝑋𝑣 は𝑣列目のこと ) 3

5.3 サンプリングの基礎 近傍頂点の中間表現の平均という集約 1 (𝑙+1) (𝑙) ℎ𝑣 = ෍ ℎ𝑢 𝒩(𝑣) 𝑢∈𝒩(𝑣) 次のような確率分布𝑝𝑣 を考える。. (𝑙+1) ℎ𝑣 = 𝐸ℎ~𝑝𝑣 [ℎ] 期待値に書き直せる (誤差はサンプリング回数Kで抑えられる) 4

5.3 サンプリング 重点サンプリング 以上の議論から𝐸𝑥~𝑝 [𝑓(𝑥)]を近似したい：重点サンプリング 提案分布𝑞と𝑥1 , … , 𝑥𝑘 ~𝑝 1 𝐾 𝑝 𝑥𝑘 𝑆𝑘 = σ𝑘=1 𝑓(𝑥𝑘 )を考える 𝐾 𝑞 𝑥𝑘 期待値の定義通りに計算すると… 𝐸𝑥~𝑝 𝑆𝑘 = 𝐸𝑥~𝑝 [𝑓(𝑥)] 1.𝑞として𝑝を用いる場合、通常のモンテカルロ 2.𝑞 𝑥 𝑝 𝑥 𝑓(𝑥) = を用いると、𝑆𝐾 は常に𝐸𝑥~𝑝 [𝑓(𝑥)] (ただし、不可能) 𝐸𝑥~𝑝 [𝑓 𝑥 ] 5

5.4 近傍サンプリング 問題設定 ● 入力 𝐺 = 𝑉, 𝐸, 𝑋 ミニバッチ𝐵 ⚫ 出力: グラフニューラルネットワークの近似値 𝑍𝑣 𝑣∈𝐵 6

5.3 近傍サンプリング 最終的に埋め込みを求めたい頂点集合Bの近傍をグ ラフニューラルの階層の数L回集めているだけ 7

5.3 近傍サンプリング 近傍集合のうち、ミニバッチ𝐵𝑙 に含まれているで 集約を行う 8

5.4 近傍サンプリング ● GraphSAGE(集約関数の部分) 9

5.4 活性値履歴を用いる方法 近傍サンプリングでは、ミニバッチに含まれない頂点は無視して いた.. ● ある頂点のミニバッチに含まれていなくとも、他の頂点のミニバ ッチには含まれている可能性 ● 10

5.4 近傍サンプリング ● 活性値履歴 11

12