Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
Understanding deeplearning, Chapter 13: Graph n...
Search
yusumi
January 16, 2024
Science
0
66
Understanding deeplearning, Chapter 13: Graph neural networks
Prince, S. J. D. (2023). Understanding Deep Learning. MIT Press.
http://udlbook.com
yusumi
January 16, 2024
Tweet
Share
More Decks by yusumi
See All by yusumi
論文紹介: Semi-Supervised Learning with Normalizing Flows
yusumi
0
11
Understanding deeplearning, Chapter 16: Normalizing flows
yusumi
1
74
Understanding deeplearning, Chapter 9: Regularization
yusumi
0
59
論文紹介 : Beyond trivial counterfactual explanations with diverse valuable explanations
yusumi
0
43
論文紹介 : Regularizing Variational Autoencoder with Diversity and Uncertainty Awareness
yusumi
0
86
Recommender Systems
yusumi
1
36
論文紹介 : Multi objective optimization of item selection in computerized adaptive testing
yusumi
0
35
Neural Networks for Sequences
yusumi
0
110
【論文紹介】Towards Unifying Feature Attribution and Counterfactual Explanations
yusumi
0
57
Other Decks in Science
See All in Science
位相的データ解析とその応用例
brainpadpr
1
620
Iniciativas independentes de divulgação científica: o caso do Movimento #CiteMulheresNegras
taisso
0
240
ultraArmをモニター提供してもらった話
miura55
0
190
白金鉱業Meetup Vol.15 DMLによる条件付処置効果の推定_sotaroIZUMI_20240919
brainpadpr
1
490
Direct Preference Optimization
zchenry
0
280
Snowflake上でRを使う: RStudioセットアップとShinyアプリケーションのデプロイ
ktatsuya
0
420
The Incredible Machine: Developer Productivity and the Impact of AI
tomzimmermann
0
390
Machine Learning for Materials (Lecture 7)
aronwalsh
0
820
はじめてのバックドア基準:あるいは、重回帰分析の偏回帰係数を因果効果の推定値として解釈してよいのか問題
takehikoihayashi
2
740
事業会社における 機械学習・推薦システム技術の活用事例と必要な能力 / ml-recsys-in-layerx-wantedly-2024
yuya4
3
230
統計的因果探索の方法
sshimizu2006
1
1.2k
20240420 Global Azure 2024 | Azure Migrate でデータセンターのサーバーを評価&移行してみる
olivia_0707
2
900
Featured
See All Featured
Fireside Chat
paigeccino
34
3k
ピンチをチャンスに:未来をつくるプロダクトロードマップ #pmconf2020
aki_iinuma
109
49k
What’s in a name? Adding method to the madness
productmarketing
PRO
22
3.1k
[RailsConf 2023] Rails as a piece of cake
palkan
52
4.9k
Fashionably flexible responsive web design (full day workshop)
malarkey
405
65k
RailsConf 2023
tenderlove
29
900
The Invisible Side of Design
smashingmag
298
50k
Designing Dashboards & Data Visualisations in Web Apps
destraynor
229
52k
Designing Experiences People Love
moore
138
23k
A Tale of Four Properties
chriscoyier
156
23k
Gamification - CAS2011
davidbonilla
80
5k
Responsive Adventures: Dirty Tricks From The Dark Corners of Front-End
smashingmag
250
21k
Transcript
Chapter 13: Graph neural networks Understanding deep learning, Prince [2023]
yusumi
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 目次 1 13.1 節: グラフとは何か? 2 13.2 節: グラフ表現 3 13.3 節: GNN の任務と損失関数 4 13.4 節: Graph convolutional networks 5 13.5 節: グラフ分類の例 6 13.6 節: 帰納モデルと転移モデル 7 13.7 節: ノード分類の例 8 13.8 節: GCN の層 9 13.9 節: エッジグラフ 10 13.10 節: まとめ Chapter 13: Graph neural networks – yusumi 2/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.1 節: グラフとは何か? Chapter 13: Graph neural networks – yusumi 3/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References グラフの例 1/2 現実には様々なグラフ構造が存在する グラフの例 ノード エッジ 交通網 建物の位置 道路 化学物質 原子 化学結合 電気回路 素子 回路 Chapter 13: Graph neural networks – yusumi 4/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References グラフの例 2/2 グラフの例 ノード エッジ SNS 人々 交友関係 学術論文 論文 引用関係 Wikipedia 記事 ハイパーリンク プログラム 構文トークン 計算 幾何学な点群 各点 近傍との接続 タンパク質相互作用 タンパク質 相互作用 集合 各要素 集合そのもの 画像 各ピクセル 近傍 8 ピクセル Chapter 13: Graph neural networks – yusumi 5/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.1.1 節: グラフの種類 Chapter 13: Graph neural networks – yusumi 6/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.1.1 節: グラフの種類 • a) 無向ブラフ: 友人関係 • b) 有向グラフ: 論文の引用関係 • c) 知識グラフ1: 異なるオブジェクト間のつながり • d) 点群: 各点が 3d 空間の位置と関連する • e) 階層グラフ: グラフ自体がノードで構成される 1directed heterogeneous multigraph とも呼ばれ, 異なる種類のノードが複数の有向エッジによりつながる Chapter 13: Graph neural networks – yusumi 7/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References グラフの種類 • a) 無向ブラフ: 友人関係 • b) 有向グラフ: 論文の引用関係 • c) 知識グラフ: 異なるオブジェクト間のつながり • d) 点群: 各点が 3d 空間の位置と関連する • e) 階層グラフ: グラフ自体がノードで構成される 本章では無向グラフにおける DNN の適用について述べる Chapter 13: Graph neural networks – yusumi 8/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.2 節: グラフ表現 Chapter 13: Graph neural networks – yusumi 9/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References グラフの埋め込み グラフ G = (V, E) は 3 つの行列に変換される: • A: グラフ構造を表す隣接行列2,{0, 1}N×N • X: ノードの埋め込み行列,RD×N • E: エッジの埋め込み行列,RDE ×E ここで,N はノード数,D は各ノードの埋め込み次元数, E はエッジ数,DE は各エッジの埋め込み次元数を表す 2通常は高次元なスパース行列となるため,非ゼロ要素をリストで管理する Chapter 13: Graph neural networks – yusumi 10/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References グラフの埋め込み例 6 つのノードと 7 つのエッジで構成されたグラフ例 Chapter 13: Graph neural networks – yusumi 11/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.2.1 節: 隣接行列の性質 AL はあるノード m ∈ V から別のノード n ∈ V まで ちょうど L 回の遷移で到達できるパスの数を表す Chapter 13: Graph neural networks – yusumi 12/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.2.2 節: 並び替え操作の不変性 ノードのインデックスを並び替えてもグラフ構造は変わらない • P の後乗算は列の並び替えに対応 • P の前乗算は行の並び替えに対応 Chapter 13: Graph neural networks – yusumi 13/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 並び替え操作の不変性 隣接行列 A は行と列の並び替え, ノード埋め込み X は列の並び替えに対応している Chapter 13: Graph neural networks – yusumi 14/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.3 節: GNN の任務と損失関数 Chapter 13: Graph neural networks – yusumi 15/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References ノードの埋め込み学習 ノードの埋め込み行列を K 層に渡って学習する Input:X, A → H1 → · · · → Hk → · · · → Output:HK Chapter 13: Graph neural networks – yusumi 16/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.3.1 節: 任務と損失関数 グラフレベルの任務 ノードの埋め込みを用いて回帰や分類問題に適用する 分類問題では,埋め込み行列はベクトルに集約され回帰される: βK ∈ R,ωK ∈ R1×D は学習可能なパラメータ,HK 1/N は行毎の平均化に対応3 3mean pooling ともいう Chapter 13: Graph neural networks – yusumi 17/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 任務と損失関数 ノードレベルの任務 各ノードにクラスラベルや連続値を割り当てる 点群のパーツ分類4などに適用される: h(n) K はノード n の埋め込み 4セクション 13.1.1 節参照,本スライドでは 2 クラス分類の場合を示す Chapter 13: Graph neural networks – yusumi 18/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 任務と損失関数 エッジ予測の任務 ノード n と m の間にエッジがあるかどうかを予測する 2 クラス分類の問題に帰着される: ノード埋め込み間の類似度 (内積) で測る Chapter 13: Graph neural networks – yusumi 19/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.4 節: Graph convolutional networks Chapter 13: Graph neural networks – yusumi 20/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References GCNs 近傍のノードを集約して新しいノード埋め込みを得る GNN の一種 各層の関数 F[•] はパラメータ Φ を持ち,ノード埋め込みと 隣接行列を引数にとり新しいノード埋め込みを得る Chapter 13: Graph neural networks – yusumi 21/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.4.1 節: 等価性と不変性 ノード・インデックスを並び替えてもグラフ構造は不変である5 k + 1 層目のノード埋め込み クラス分類 ベクトルを集約すると並び替え操作の影響は無視される CNN に比べて特徴の等価性や不変性を定義しやすい 513.2.2 節を参照 Chapter 13: Graph neural networks – yusumi 22/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.4.2 節: パラメータの共有 全結合層 • 各ノードは独立し,並び替え操作に不変ではない • 帰納バイアス6を学習する必要がある 畳み込み層 • 近傍情報の集約を用いた帰納バイアスの考慮 • 近傍情報の範囲はどの位置でも不変 グラフ畳み込み層 • 近傍情報の集約を用いた帰納バイアスの考慮 • 近傍情報の範囲は位置によって異なる 6画像の近傍ピクセルや隣接ノードとの依存関係を指す Chapter 13: Graph neural networks – yusumi 23/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.4.3 節: グラフ畳み込み層の例 第 k 層のノード n は,その隣接ノードを集約して得られる: ne[n] はノード n の隣接ノード集合を表す この集約を用いてノード n の k + 1 層目の埋め込みが得られる: βk と Ωk は学習可能なパラメータ Chapter 13: Graph neural networks – yusumi 24/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References グラフ畳み込みと隣接行列の関係 全ノードについて層の更新をまとめると以下になる: 1 は全ての要素を 1 とするベクトル,a[•] は活性化関数 agg[n, k] は埋め込み行列 Hk の n 行目と 隣接行列 A の k 行目の内積に対応していた! Chapter 13: Graph neural networks – yusumi 25/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References グラフ畳み込みの伝播 Chapter 13: Graph neural networks – yusumi 26/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.5 節: グラフ分類の例 Chapter 13: Graph neural networks – yusumi 27/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 分子構造の分類 特定の分子構造が有害か無害かを判定する問題に適用してみよう Input: A, X • A ∈ RN×N: 分子構造を表す隣接行列 • X ∈ R118×N: 周期表 118 元素の存在に関する OneHot 表現 X は最初の層で重みパラメータ Ω0 ∈ RD×118 により, Ω0X ∈ RD×N に変換される Chapter 13: Graph neural networks – yusumi 28/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 分子構造の分類 Input: A, X • A ∈ RN×N: 分子構造を表す隣接行列 • X ∈ R118×N: 周期表 118 元素の存在に関する OneHot 表現 f[X, A, Φ] は分子が有毒である確率を返す Chapter 13: Graph neural networks – yusumi 29/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.5.1 節: バッチ単位での学習 グラフをバッチ単位に分割する • 訓練用グラフ {Xi, Ai}I i=1 とラベル yi • パラメータ Φ = {βk, Ωk}K k=0 グラフ全体をバッチ並列処理することは可能か? (Xi , Ai はバッチに応じてサイズが異なり結合が困難) Chapter 13: Graph neural networks – yusumi 30/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.5.1 節: バッチ単位での学習 グラフをバッチ単位に分割する • 訓練用グラフ {Xi, Ai}I i=1 とラベル yi • パラメータ Φ = {βk, Ωk}K k=0 グラフ全体をバッチ並列処理することは可能か? (Xi , Ai はバッチに応じてサイズが異なり結合が困難) 可能 最終層の mean pooling を施すことでサイズに よらずグラフ毎の単一表現7を得ることができる 7損失関数を計算するための確率予測値 Chapter 13: Graph neural networks – yusumi 31/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.6 節: 帰納モデルと転移モデル Chapter 13: Graph neural networks – yusumi 32/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 帰納 vs. 転移 帰納モデル (inductive models) • ラベル付きの訓練データを用いて入出力関係を学習する • 学習したルールを新しいテストデータに適用する 転移モデル (transductive models) • ラベル付き/無しデータの両方を同時に考慮する8 • 未知の出力に対してのみラベリングを行う • ラベルなしデータが追加されると再訓練する必要がある • グラフレベルの任務では帰納モデルのみが適用される • ノードレベルの任務では帰納と転移モデル両方が適用できる 8半教師あり学習とも呼ばれる Chapter 13: Graph neural networks – yusumi 33/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References ノードレベルの任務における帰納と転移モデル a) 複数のグラフが与えられる b) 単一のグラフのみが与えられる • a) 帰納モデル: ラベル付き訓練グラフが与えられ,学習後に テストグラフの各ノードラベルを予測する • b) 転移モデル: ラベル付き/無しのグラフが与えられ,ラベル付き のノード予測を学習した後にラベル無しノードを予測する Chapter 13: Graph neural networks – yusumi 34/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.7 節: ノード分類の例 Chapter 13: Graph neural networks – yusumi 35/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References ノードレベルの任務における転移モデル 転移モデルにおけるノード分類の学習について紹介する 最終層の出力9 sig[•] は各ノードに sigmoid 関数を適用する,HK ∈ RD×N 損失関数 • クロスエントロピー誤差関数 大規模データを想定し,ノード数 N は数百万規模とする 913.3.1 節をノード数分の次元に拡張 Chapter 13: Graph neural networks – yusumi 36/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 膨大なノード数で発生する問題 転移モデルに大規模ノードを適用すると 2 つの問題が生じる: 問題 1 • メモリ効率が悪い • 膨大なノード数を GNN の各層に保存する必要がある 問題 2 • 確率的勾配降下法の適用が困難 • グラフが 1 つしかないためバッチの分割が難しい Chapter 13: Graph neural networks – yusumi 37/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.7.1 節: バッチの選択 問題に対する解決策 ラベル付きノード集合のランダムな部分集合を選択する • バッチノード毎に k − hop 近傍10を集約する • 集約結果を全バッチでまとめて損失関数を計算する GNN の層数 k で k − hop 近傍を考慮できる CNN の受容野と等価な機能を持つ 10注目ノードから k ステップ以内で到達可能なノード集合 Chapter 13: Graph neural networks – yusumi 38/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References バッチ選択の問題 バッチ選択にも問題が存在する 問題 • グラフが密すぎるとバッチにほぼ全てのノードが含まれる11 • GNN の層数が多すぎるとほぼ全てのノードを参照する バッチ分割する意味が無くなってしまう12 11完全グラフなど 12graph expansion problem と呼ばれる Chapter 13: Graph neural networks – yusumi 39/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References バッチ選択の問題に対する対処 近傍サンプリング (neighborhood sampling) • 近傍ノード集合の一部を適当にサンプリングする • エポック毎にサンプリングされるノードは異なる • ドロップアウトと同様の正則化効果を得られる グラフ分割 (graph partitioning) • グラフをクラスタリングする • 各グラフは互いに接続させない13 • 各グラフをバッチとして扱うことができる 13k − hop 近傍を調べる時に全ノードを参照しないようにする Chapter 13: Graph neural networks – yusumi 40/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 近傍サンプリングの例 k − hop 近傍 • a) 単純なバッチ選択 • b) 近傍サンプリング 色の濃さは 注目ノードとの近さ ※深い層から確認する方が 分かりやすい Chapter 13: Graph neural networks – yusumi 41/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References グラフ分割の例 a) 入力グラフ b) グラフ分割14 c)–e) 各グラフの活用例 c)–d) バッチとして利用する場合を想定 e) グラフ同士を 1 つのバッチとして扱う 14クラスター間のエッジは削除 Chapter 13: Graph neural networks – yusumi 42/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.8 節: GCN の層 Chapter 13: Graph neural networks – yusumi 43/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 更新式の見直し 今までの議論で GCN の各層は以下の更新式を用いた15: Hk+1 = a[βk1 + ΩkHk(A + I)] 前層のノード埋め込み Hk に A + I を掛けることで達成 本節では更新式に 2 つの変更を取り入れる 拡張案 1 現在のノードの変更 2 集約プロセスそのものの変更 1513.4.3 節を復習 Chapter 13: Graph neural networks – yusumi 44/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 集約方法の再検討 1 13.8.1 節: 現在のノードの変換 2 13.8.2 節: 残差接続 3 13.8.3 節: 平均集約 4 13.8.4 節: Kipf 正規化 5 13.8.5 節: Max プーリング集約 6 13.8.6 節: Attention 集約 Chapter 13: Graph neural networks – yusumi 45/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 集約方法の再検討 1 13.8.1 節: 現在のノードの変換 2 13.8.2 節: 残差接続 3 13.8.3 節: 平均集約 4 13.8.4 節: Kipf 正規化 5 13.8.5 節: Max プーリング集約 6 13.8.6 節: Attention 集約 Chapter 13: Graph neural networks – yusumi 46/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.8.1 節: 現在のノードの変換 現在のノードにノイズ (1 + k) を加える16 → 過学習の抑制効果 現在のノードを Ψk で線形変換する → 表現力の向上 Ωk = [Ωk , Ψk ] でまとめている 16diagonal enhancement とも呼ばれる Chapter 13: Graph neural networks – yusumi 47/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 集約方法の再検討 1 13.8.1 節: 現在のノードの変換 2 13.8.2 節: 残差接続 3 13.8.3 節: 平均集約 4 13.8.4 節: Kipf 正規化 5 13.8.5 節: Max プーリング集約 6 13.8.6 節: Attention 集約 Chapter 13: Graph neural networks – yusumi 48/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.8.2 節: 残差接続 現在のノードは隣接ノードの非線形変換と結合される Chapter 13: Graph neural networks – yusumi 49/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 集約方法の再検討 1 13.8.1 節: 現在のノードの変換 2 13.8.2 節: 残差接続 3 13.8.3 節: 平均集約 4 13.8.4 節: Kipf 正規化 5 13.8.5 節: Max プーリング集約 6 13.8.6 節: Attention 集約 Chapter 13: Graph neural networks – yusumi 50/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.8.3 節: 平均集約 グラフ構造よりも埋め込み情報の方が重要な場合, 総和よりも平均の方が優れる可能性がある 近傍の寄与の大きさが近傍の数に依存しない Chapter 13: Graph neural networks – yusumi 51/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 平均集約 グラフ構造よりも埋め込み情報の方が重要な場合, 総和よりも平均の方が優れる可能性がある 近傍の寄与の大きさが近傍の数に依存しない 平均集約によるノード埋め込みの更新式は以下になる: D は隣接ノードの個数を要素に持つ対角行列 D−1 は平均の分母を要素に持つ対角行列 Chapter 13: Graph neural networks – yusumi 52/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 集約方法の再検討 1 13.8.1 節: 現在のノードの変換 2 13.8.2 節: 残差接続 3 13.8.3 節: 平均集約 4 13.8.4 節: Kipf 正規化 5 13.8.5 節: Max プーリング集約 6 13.8.6 節: Attention 集約 Chapter 13: Graph neural networks – yusumi 53/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.8.4 節: Kipf 正規化 多くの隣接ノードを持つノードからの重みを小さくする 接続が多いノードからの情報はユニーク性に欠ける17 17自身のノード情報が少ない Chapter 13: Graph neural networks – yusumi 54/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References Kipf 正規化 多くの隣接ノードを持つノードからの重みを小さくする 接続が多いノードからの情報はユニーク性に欠ける18 Kipf 正規化によるノード埋め込みの更新式は以下になる: D は隣接ノードの個数を要素に持つ対角行列 18自身のノード情報が少ない Chapter 13: Graph neural networks – yusumi 55/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 集約方法の再検討 1 13.8.1 節: 現在のノードの変換 2 13.8.2 節: 残差接続 3 13.8.3 節: 平均集約 4 13.8.4 節: Kipf 正規化 5 13.8.5 節: Max プーリング集約 6 13.8.6 節: Attention 集約 Chapter 13: Graph neural networks – yusumi 56/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.8.5 節: Max プーリング集約 Max プーリングもノードの並び替えの影響を受けない max[•] は要素ごとに最大値を返す Chapter 13: Graph neural networks – yusumi 57/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 集約方法の再検討 1 13.8.1 節: 現在のノードの変換 2 13.8.2 節: 残差接続 3 13.8.3 節: 平均集約 4 13.8.4 節: Kipf 正規化 5 13.8.5 節: Max プーリング集約 6 13.8.6 節: Attention 集約 Chapter 13: Graph neural networks – yusumi 58/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.8.6 節: Attention 集約 Graph attention 層を用いるとノードの更新は以下になる はじめに,現在のノード埋め込みを線形変換する: Hk = βk1 + ΩkHk Chapter 13: Graph neural networks – yusumi 59/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References ノード間類似度の計算 次に,ノード間の類似度 smn を計算する: m, n はインデックス,φk は学習可能なパラメータ,a[•] は活性化関数 Chapter 13: Graph neural networks – yusumi 60/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References ノード埋め込みの更新 smn を要素に持つ行列を S とすると,最終的な更新式は以下: a[•] は活性化関数 Softmask[•, •] は第一引数 S の各列に softmax 関数を適用するが, 適用前に第二引数 A + I が 0 の位置の要素 (非隣接) を −∞ にする前処理を伴う 隣接ノードの注目度のみ考慮し,非隣接ノードの注目度はゼロになる Chapter 13: Graph neural networks – yusumi 61/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References Graph attention network の考え方 ノードの線形変換と self-attention の組合せと考えることができる 線形変換のみを導入 Self-attention のみを導入 (隣接行列は考慮しない) Chapter 13: Graph neural networks – yusumi 62/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.9 節: エッジグラフ Chapter 13: Graph neural networks – yusumi 63/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References エッジグラフとノードグラフの関係 エッジ埋め込みはエッジグラフを構築することで学習可能である エッジグラフの構築方法 a) 6 つのノードで構成された通常のグラフ (オレンジ色) b) エッジに対応するノードを追加する (青色) c) エッジノード同士を結合する 通常のグラフと同様に学習することができる19 19通常のノードとエッジノードの学習を組合せることも可能 Chapter 13: Graph neural networks – yusumi 64/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 13.10 節: まとめ Chapter 13: Graph neural networks – yusumi 65/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References GNN のまとめ 世の中の多くの現象はグラフに落とし込むことができる • GNN はグラフにニューラルネットワークを適用した手法 • GNN のノードは順不同である • CNN は GNN の一種と見なせる • ノードとエッジを入れ替えても学習できる GNN の課題 • 多くのグラフ構造は転移的な設定である • グラフの構造は大規模になりやすい • グラフの分割アルゴリズムは検討の余地がある Chapter 13: Graph neural networks – yusumi 66/67
13.1 節 13.2 節 13.3 節 13.4 節 13.5 節
13.6 節 13.7 節 13.8 節 13.9 節 13.10 節 References 参考文献 I [1] Simon J.D. Prince. Understanding Deep Learning. MIT Press, 2023. URL https://udlbook.github.io/udlbook/. Chapter 13: Graph neural networks – yusumi 67/67