【グラフニューラルネットワーク】1.4~1.7

2024前期輪読会#1 グラフニューラルネットワーク1.4~1.7 京都大学理学部 二回 千葉 一世 0

GNNでのグラフデータの処理方法 1

GNNでのグラフデータの処理 GNNでは、メッセージ伝達という機構を用いてグラフを処理する。 メッセージ伝達のイメージ グラフ上で辺で結ばれた頂点は似たような性質を持っているという 考えから、隣接頂点の情報を取り入れながら計算する。 例 : オンライン広告でどの商品の広告を表示するか 従来のDNN GNN A A B B C C D A～Dさんの閲覧履歴などから個別に予測 D 友達同士の好みは似ているだろうという考えから、 友達の閲覧履歴も利用して予測 2

GNNでのグラフデータの処理 メッセージ伝達の考え方は畳み込み層に似ている 畳み込み 画像データでは、隣接する画素は 同じ物体を表している 隣接した画素も含めて考えよう メッセージ伝達 グラフデータでは、辺で結ばれた点は 似た性質を持っている 隣接した頂点の情報も併せて考えよう 3

GNNでのグラフデータの処理 メッセージ伝達の例 uが好き 監督はb 原作者はa uと友達 一度目のメッセージ伝達で、 u’はuの友達であること・ 映画vはuが好きなことが伝わり、 u’に映画vをお勧めする。 (社交的推薦) 推薦 監督はb 自分の好きな映画vは 監督がbで、原作者がa 二度目のメッセージ伝達で、 uに好きな映画vの監督がbであること 映画v‘の監督がbであることが伝わり、 uに映画v‘をお勧めする。 (知識グラフの利用) 4

ベンチマーク用データセット 頂点 辺a⇒b 頂点特徴量 辺特徴量 Cora CiteSeer PubMed 論文 aがbを引用 論文内容の単 語集合 論文のカ テゴリ 頂点分類 Amazon Computers 商品 aとbが一緒に購 入されやすい 商品レビュー の単語集合 商品のカ テゴリ 頂点分類 Reddit 投稿 同じユーザーが aとbにコメント をした 投稿のタイト ル・コメン ト・投稿のス コア・コメン ト数 投稿の属 するサブ レディッ ト 頂点分類 PPI タンパク質 aとbの間に相互 作用が存在 関連する遺伝 子情報 タンパク 質の機能 頂点分類 FB15ｋ 事物 aとbに関係があ る PROTEINS タンパク質 の二次構造 aとbがアミノ酸 配列で隣接 or 近くに存在 二次構造の種 類 QM9 ZINC MUTAG 原子 ab間の化学結合 原子の種類 頂点ラベ ル 辺ラベル グラフラ 用途 ベル aとbの関 係の種類 化学結合 の種類 接続予測 酵素か どうか グラフ分 類 化合物 の特性 グラフ回 帰 5

テキスト上の記号 ● I,J ⊂[n]を行,列の添え字集合として、 行列 𝑨𝐈,𝑱 を、AのI行,J列だけを並べた行列とする 𝐴= ● 2 −1 0 −1 1 1 5 2 3 0 −2 0 1 2 −1 0 −1 3 0 2 0 2 −1 −3 3 2 0 4 −4 1 6 −5 1 0 2 1 , I = {1,2,4,6}, J = {2,3,5}として、 𝑨𝑰,𝑱 = −𝟏 𝟎 𝟏 𝟓 𝟐 −𝟏 𝟐 −𝟏 𝟑 𝟎 𝟔 𝟐 添え字集合のコロン表記 :a = [a] = {1,2,…,a}, a: = {a,a+1,…,n}, a:b = {a,a+1,…,b} Pythonのスライスの表記と似ているが、a: がaを含むことに注意 6

テキスト上の記号 ● 多重集合 {{・}} : 重複を考慮する集合、それ以外は集合と同じ {{2,3,3}} ≠ {{2,3}} 重複度が異なるので、別の集合 {{2,3,3}} = {{3,2,3}} 順序は考えないので、同じ集合 ෍ 𝑥∈{ 2,3,3 } 𝑥 =2+3+3=8 総和などで、多重集合から要素を 取り出して演算するときは、 重複度分取り出す 7

テキスト上の記号 ● Aを隣接行列、Bを接続行列、Dを次数行列 2 𝑨= 𝟎 𝟏 𝟏 𝟏 𝟎 𝟏 𝟎 𝟏 𝟎 𝟏 𝟏 𝟏 𝟎 𝟎 𝟏 𝟏 𝟎 𝟎 𝟎 𝟏 1 ● ● 𝟎 𝟏 𝟏 , 𝟏 𝟎 𝐁= 𝟏 𝟏 𝟎 𝟎 𝟎 𝟏 𝟎 𝟏 𝟎 𝟎 𝟎 𝟏 𝟏 𝟎 𝟎 𝟏 𝟎 𝟎 𝟏 𝟎 𝟎 𝟎 𝟏 𝟎 𝟏 ● 𝟎 𝟎 𝟎 , 𝟏 𝟏 𝑫= 𝟑 𝟎 𝟎 𝟎 𝟎 𝟎 𝟑 𝟎 𝟎 𝟎 𝟎 𝟎 𝟑 𝟎 𝟎 𝟎 𝟎 𝟎 𝟐 𝟎 𝟎 𝟎 𝟎 𝟎 𝟑 ４ 1 ３ 7 5 3 ５ ２ 6 1 𝐴መ = 𝐷 𝐴 𝐷 を対称正規化隣接行列 𝐿 = 𝐷 − 𝐴 をグラフラプラシアン(ラプラシアン行列) −2 −2 1 ● 𝟎 𝟏 𝟎 𝟎 𝟏 4 １ 1 𝐿𝑠𝑦𝑚 = 𝐿𝑠𝑦𝑚 = 𝐼𝑛 − 𝐴መ = 𝐷 𝐿𝐷 を対称正規化ラプラシアン 𝐿𝑟𝑤 = 𝐿𝑟𝑤 = 𝐼𝑛 − 𝐷−1 𝐴 = D−1 L を推移ラプラシアン −2 −2 ・∆との関係 ∆ = 𝒅𝒊𝒗(𝒈𝒓𝒂𝒅) 𝐿 = 𝐷 − 𝐴 = 𝐵𝐵𝑇 が成り立ち、グラフ上の関数 𝑓 ∶ 𝑉 → ℝ への作用を考えると、 𝑩は𝒅𝒊𝒗 、𝑩𝑻 は𝒈𝒓𝒂𝒅に対応している 8

テキスト上の記号 ● ビッグ・オー 𝒇 𝒙 =𝑶 𝒈 𝒙 ● ≤ 𝑴|𝒈(𝒙)| f(x)はg(x)以下の速度で大きくなる関数。 ビッグ・オメガ 𝒇 𝒙 =𝛀 𝒈 𝒙 ● 𝒇 𝒙 ⟺ 𝒍𝒊𝒎 𝒔𝒖𝒑𝒙→∞ <∞ 𝒈 𝒙 ⟺∃ 𝒙𝟎 , ∃ 𝑴 > 𝟎 𝒔. 𝒕. ∀ 𝒙 > 𝒙𝟎 , 𝒇 𝒙 𝒇 𝒙 ⟺ 𝒍𝒊𝒎 𝒊𝒏𝒇𝒙→∞ >𝟎 𝒈 𝒙 ⟺∃ 𝒙𝟎 , ∃ 𝑴 > 𝟎 𝒔. 𝒕. ∀ 𝒙 > 𝒙𝟎 , 𝑴 𝒈(𝒙) ≤ |𝒇(𝒙)| f(x)はg(x)以上の速度で大きくなる関数。 ビッグ・シータ 𝒇 𝒙 = 𝚯 𝒈 𝒙 ⟺ 𝒇 𝒙 = 𝑶 𝒈 𝒙 かつ 𝒇 𝒙 = 𝛀 𝒈 𝒙 f(x)はg(x)と同じくらいの速度で大きくなる関数。 9

2. 便利なテンプレ集 この本の流れ 2章 グラフ理論の基礎と古典的なグラフ機械学習 3章 GNNの基本事項 : GNNの定式化、訓練・推論方法 4章 様々なタスクへの応用 5章 6章 7章 8章 GNNの高速化・省コスト化 スペクトルグラフ理論 過平滑化現象と対策 GNNの表現能力の限界 10