![[DL輪読会]Flow-based Deep Generative Models](https://cdn.slidesharecdn.com/ss_thumbnails/20190307-190328024744-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]Neural Ordinary Differential Equations](https://cdn.slidesharecdn.com/ss_thumbnails/nnasode1-190111001755-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]Set Transformer: A Framework for Attention-based Permutation-Invariant...](https://cdn.slidesharecdn.com/ss_thumbnails/20200221settransformer-200221020423-thumbnail.jpg?width=560&fit=bounds)
![[DL輪読会]World Models](https://cdn.slidesharecdn.com/ss_thumbnails/20180427-180427003856-thumbnail.jpg?width=560&fit=bounds)
More Related Content
What's hot (20)
Similar to Graph convolution (スペクトルアプローチ) (20)
More from yukihiro domae (8)
Graph convolution (スペクトルアプローチ)
- 2. ? ?：隣接行列 ? ノードの接続を表す行列 ? 隣接リスト ? ノードの接続を表すリスト ? ?：次数行列 ? 各節点の次数を対角上に並べた対角行列 Graphを表現するための行列 2 4 0 0 0 0 0 2 0 0 0 0 0 2 0 0 0 0 0 1 0 0 0 0 0 3 ? ? ? ? ? ? ? ?? ? ? ? ? ? ?? ? D ? ? ? ? ? ? ? ? ? ? ? ? 1,2,3,4 0,4 0,4 0,4 0 0,1,2 隣接行列 隣接リスト 次数行列
- 3. グラフフーリエ変换
- 4. ? グラフラプラシアンの固有ベクトルによるグラフ信号の展開 ? 固有値 λ? ：グラフ周波数 ? 固有ベクトル ?λ ? ：フーリエ基底 ? 基底ベクトルと内積をとるとその方向の成分を取り出せる ? その周波数成分が取り出せる グラフフーリエ変换 4 ノード情報 ? フーリエ基底?λ ? 周波数λ?の成分
- 5. ? ? :非正規化ラプラシアン ? = ? ? ? ? ? ：正規化グラフラプラシアン ? = ?? ? ? ??? ? ? = ? ? ?? ? ? ??? ? ? ? 正規?非正規化ラプラシアンの違い ? 非正規化ラプラシアン : 固有値の最大値が変化 ? 正規化ラプラシアン : 固有値の最大値が2以下（正規化） (正規?非正規化ラプラシアンの固有値はどちらも0以上) グラフラプラシアン 5
- 6. ? ? ：入力（ノード情報） ? ? ：隣接行列 ? ? ：次数行列 ? ? ：グラフラプラシアン ? λ? ：?の固有値 ? ?λ ? ：?の固有ベクトル ? ? ：?の固有ベクトルを並べた行列 ? ? :グラフのノード数 グラフフーリエ変换 ? = ? ? ? 上式の関数(固有値 i に対する信号) ?(??) = ?=? ??? ?(?)? ? ? ? (?) 逆グラフフーリエ変换 ? = ?? 上式の関数(ノード jk の情報) ?(?) = ?=? ??? ?(??)? ? ? (?) グラフフーリエ変换 6 ノード情報 ? は各ノード1次元
- 7. グラフフーリエ変换 ? = ? ? ? 上式の関数(固有値iに対する信号) ?(??) = ?=? ??? ?(?)? ? ? ? (?) 逆グラフフーリエ変换 ? = ?? 上式の関数(ノードkの情報) ?(?) = ?=? ??? ?(??)? ? ? (?) グラフフーリエ変换 7 ? = ?(0) ?(1) ?(2) 固有ベクトル ノード情報 ? = ? ?0 (0) ? ?1 (0) ? ?2 (0) ? ?0 (1) ? ?1 (1) ? ?2 (1) ? ?0 (2) ? ?1 (2) ? ?2 (2) ? ? = ? ?0 (0) ? ?0 (1) ? ?0 (2) ? ?1 (0) ? ?1 (1) ? ?1 (2) ? ?2 (0) ? ?2 (1) ? ?2 (2) ? ? ? = ? ?0 (0) ? ?0 (1) ? ?0 (2) ? ?1 (0) ? ?1 (1) ? ?1 (2) ? ?2 (0) ? ?2 (1) ? ?2 (2) ?(0) ?(1) ?(2) = ?0 ? ?1 ? ?2 ? = ? ?0 ? ?1 ? ?2 グラフ周波数λ ?に対する信号 ?0 ?
- 8. グラフフーリエ変换 ? = ? ? ? 上式の関数(固有値iに対する信号) ?(??) = ?=? ??? ?(?)? ? ? ? (?) 逆グラフフーリエ変换 ? = ?? 上式の関数(ノードkの情報) ?(?) = ?=? ??? ?(??)? ? ? (?) グラフフーリエ変换 8 ? = ?(0) ?(1) ?(2) 固有ベクトル ノード情報 ? = ? ?0 (0) ? ?1 (0) ? ?2 (0) ? ?0 (1) ? ?1 (1) ? ?2 (1) ? ?0 (2) ? ?1 (2) ? ?2 (2) ? ? = ? ?0 (0) ? ?0 (1) ? ?0 (2) ? ?1 (0) ? ?1 (1) ? ?1 (2) ? ?2 (0) ? ?2 (1) ? ?2 (2) ?? = ? ?0 (0) ? ?1 (0) ? ?2 (0) ? ?0 (1) ? ?1 (1) ? ?2 (1) ? ?0 (2) ? ?1 (2) ? ?2 (2) ? ?0 ? ?1 ? ?2 = ?(0) ?(1) ?(2)
- 9. スペクトル上でのフィルタリング ? それぞれの周波数別の信号にフィルタをかける (周波数 ?0 上の信号 ?0 ?に対してフィルタ ?(?0) をかける) ? ?(??) は固有値??（グラフ周波数）に対する関数 9 0 1 1 ( ) ( ) ( ) T N H H H ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? U U f フィルタ スペクトル上でのフィルタリング ?(?0) 0 0 0 ?(?1) 0 0 0 ?(?2) ?0 ? ?1 ? ?2 ? = ?(?0)?0 ? ?(?1)?1 ? ?(?2)?2 ?
- 10. 10 空間上でのフィルタリング ?(?) = ? ?? ? ? + ?? ? ? ? ?? ?(?) ? ? : ノード ? の周辺ノードの集合 ? ??, ? ?? : フィルタ係数 ?(?) : フィルタリング後のノード ? のノード情報 ? 上式と同じことをスペクトル上でも行えることを式で示す 注目ノード 隣接ノード グラフの空間上でのフィルタリング
- 11. 11 注目ノード隣接ノードをまとめる ?(?) = ? ?? ? ? + ?? ? ? ? ?? ?(?) = ?? ? ? ? ?? ?(?) ? ? : ノード ? の周辺ノードの集合（注目ノードも含む） ? ?? : フィルタ係数 ?(?) : フィルタリング後のノード ? のノード情報 ? 上式と同じことをスペクトル上でも行えることを式で示す グラフの空間上でのフィルタリング 注目ノード 隣接ノード
- 12. 12 スペクトル上でのフィルタリング スペクトル上でのフィルタリング 上の式を書き換え ?(?) = ?=0 ??1 ?(??) ?(??)? ? ? (?) ?(??) = ?=? ??? ?(?) ? ? ? ? (?) 0 1 1 ( ) ( ) ( ) T N H H H ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? U U f フィルタ グラフ上のフーリエ変換 ? ?0 (0) ? ?1 (0) ? ?2 (0) ? ?0 (1) ? ?1 (1) ? ?2 (1) ? ?0 (2) ? ?1 (2) ? ?2 (2) ?(?0) 0 0 0 ?(?1) 0 0 0 ?(?2) ? ?0 ? ?1 ? ?2 = ? ?0 (0) ? ?1 (0) ? ?2 (0) ? ?0 (1) ? ?1 (1) ? ?2 (1) ? ?0 (2) ? ?1 (2) ? ?2 (2) ?(?0)? ?0 ?(?1)? ?1 ?(?2)? ?2 = ? 0 ? 1 ? 2 ? ? = ? ?0 (0) ? ?0 (1) ? ?0 (2) ? ?1 (0) ? ?1 (1) ? ?1 (2) ? ?2 (0) ? ?2 (1) ? ?2 (2) ?(0) ?(1) ?(2) = ? ?0 ? ?1 ? ?2
- 13. スペクトル上のフィルタがλのk次多項式と仮定 ? ?? = ?=0 ? ? ? ?? ? 13 スペクトル上でのフィルタリング スペクトル上でのフィルタリング 上の式を書き換え ?(?) = ?=0 ??1 ?(??) ?(??)? ? ? (?) ?(??) = ?=? ??? ?(?) ? ? ? ? (?) 0 1 1 ( ) ( ) ( ) T N H H H ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? U U f フィルタ グラフ上のフーリエ変換
- 14. 14 スペクトル上でのフィルタリング ?(?) = ?=0 ??1 ?(??) ?(??)? ? ? (?) λのk次多項式フィルタ ? ?? = ?=0 ? ? ? ? ? グラフ上のフーリエ変換 ?(??) = ?=0 ??1 ?(?) ? ? ? ? (?) 空間上でのフィルタリング ?(?) = ? ?? ? ? + ?? ? ? ? ?? ?(?) 1 0 ( ) ( ) ( ) ( )i N i ii f k F H u k ? ? ? ? ? λλ λ 1 1 * 0 0 0 ( ) ( ) ( )i i N K N p ij p i f j u j u k ? ? ? ? ? ? ? ? ?p λ λα λ スペクトル上でのフィルタリング
- 15. ? 橙枠はグラフラプラシアン L の p 乗 ? ? = ?? ? ? ? 1 1 * 0 0 0 1 0 0 ( ) ( ) ( ) ( ) ( ) i i N K N p ij p i N K p kjj p f j u j u k f j L ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? p λ λ p α λ α 1 0 ( ) ( ) ( ) ( )i N i ii f k F H u k ? ? ? ? ? λλ λ 15 スペクトル上でのフィルタリング スペクトル上でのフィルタリング ?(?) = ?=0 ??1 ?(??) ?(??)? ? ? (?) λのk次多項式フィルタ ? ?? = ?=0 ? ? ? ? ? グラフ上のフーリエ変換 ?(??) = ?=0 ??1 ?(?) ? ? ? ? (?) 空間上でのフィルタリング ?(?) = ? ?? ? ? + ?? ? ? ? ?? ?(?)
- 16. ? 橙枠はグラフラプラシアン L の p 乗 ? ? = ?? ? ? ? 1 1 * 0 0 0 1 1 * 0 0 0 1 0 0 ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) i i i i N N K p ii j p N K N p ij p i N K p kjj p f j u j u k f j u j u k f j L ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? λ p λ p λ λ p α λ α λ α 1 0 ( ) ( ) ( ) ( )i N i ii f k F H u k ? ? ? ? ? λλ λ 16 スペクトル上でのフィルタリング ? ? = ? ?0 (0) ? ?0 (1) ? ?0 (2) ? ?1 (0) ? ?1 (1) ? ?1 (2) ? ?2 (0) ? ?2 (1) ? ?2 (2) ?0 ? 0 0 0 ?1 ? 0 0 0 ?2 ? ? ?0 ? (0) ? ?1 ? (0) ? ?2 ? (0) ? ?0 ? (1) ? ?1 ? (1) ? ?2 ? (1) ? ?0 ? (2) ? ?1 ? (2) ? ?2 ? (2) = ? ?0 (0) ? ?0 (1) ? ?0 (2) ? ?1 (0) ? ?1 (1) ? ?1 (2) ? ?2 (0) ? ?2 (1) ? ?2 (2) ? ?0 ? (0)?0 ? ? ?1 ? (0)?0 ? ? ?2 ? (0)?0 ? ? ?0 ? (1)?1 ? ? ?1 ? (1)?1 ? ? ?2 ? (1)?1 ? ? ?0 ? (2)?2 ? ? ?1 ? (2)?2 ? ? ?2 ? (2)?2 ?
- 17. スペクトル上でのフィルタリング ? ? = ?? ? ? ? ? ?? = ?=0 ? ? ?(? ?) ?? 空間上でのフィルタリング ?(?) = ?? ? ? ? ?? ?(?) ? スペクトル上でも空間上でのフィルタリングと 同じことを行うことが可能であると示された 空間上でのフィルタリング ? 注目ノードとその隣接ノードにフィルタ係数を かけて和を求めること 17 スペクトル上でのフィルタリング 1 1 * 0 0 0 1 0 0 ( ) ( ) ( ) ( ) ( ) i i N K N p ij p i N K p kjj p f j u j u k f j L ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? p λ λ p α λ α 1 0 ( ) ( ) ( ) ( )i N i ii f k F H u k ? ? ? ? ? λλ λ (1) (2) ? ?? スペクトル領域上でフィルタ (式1) ? ?? 空間上でのフィルタ (式2) ＝
- 18. スペクトル領域上での畳み込み ? = ?? ? ? ? ? ? = ? ? ??? ? ? = ? ? ? ? ? フィルタ? ?(?) ? ?(?)= ?=0 ??1 ? ? ? ? ? ? ?? を学習することで， 注目ノードからKステップ離れたノードまで を畳み込む グラフ上でのフィルタリングからグラフ上の畳み込みへの導出 18 スペクトル領域上でのフィルタリング ? フィルタ ? ?? ? ?? = ?=0 ? ? ?(? ?) ?? ? ノードkに対してpステップで行ける ノードに対してフィルタリングできる 1 1 * 0 0 0 1 0 0 ( ) ( ) ( ) ( ) ( ) i i N K N p ij p i N K p kjj p f j u j u k f j L ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? p λ λ p α λ α 1 0 ( ) ( ) ( ) ( )i N i ii f k F H u k ? ? ? ? ? λλ λ
- 20. ? = ?? ? ? ? ? ? = ? ? ? ? ? フィルタ? ?(?) ? ?(?)= ?=0 ??1 ? ? ? ? ? ? ?（k = 0 ~ K-1）を学習される重み ? 注目ノードからkステップ離れたノードまでを畳み込む ? 1回畳み込みこむために? ? の計算を行う必要がある （? ? はノード数の 2 乗の k 乗の計算量） ? 層を重ねると計算量が増大 スペクトル領域上での畳み込み 20 フーリエ変換 フーリエ逆変換
- 21. スペクトル領域上での畳み込み ? = ?? ? ? ? ? ? = ? ? ? ? ? フィルタ? ?(?) ? ?(?)= ?=0 ??1 ? ? ? ? ? ? ?（k = 0 ~ K-1）を学習することで， 注目ノードからkステップ離れたノードまで を畳み込む Chevnetについて 21 Chevnetの畳み込みは ? ?(?) をチェビシェフ多項式T? ( ?)に置換 ? ?(?) ? = ?=0 ??1 ? ?T? ( ?) ? T? ? = 2 ?T??1( ?) - T??2( ?) ? T0 ? = 1, T1 ? = ? ? グラフラプラシアンをリスケーリング ? ? = 2 ? ??? ? ? ? ?
- 22. ? 正規化ラプラシアン ? 固有値 ? が 0 ~ 2 までの範囲になる ?? ? ? ??? ? ? ? ? について ? 固有値 ? が -1 ~ 1 までの範囲になる ? = 2 ? ??? ? ? ? ? ? について 22
- 23. ? = ? ? ? ? = ? ? ??? ? ? = ?? ? ? ? ? ? ? スペクトル上での畳み込みは 1. ノードの情報のフーリエ変換 → 各基底（固有ベクトル）上の信号に変換 2. 基底別（固有値別）にフィルタをかける 3. 逆フーリエ変換（固有ベクトルの積） Chevnetでの ? ? ? は ?? ?(?)? ? ? = ?=0 ??1 ? ? ?T? ( ?)? ? ? 固有値との関係 23 T? ? ① ② ③
- 24. グラフ構造の変化に弱い ? グラフ構造が変化すると基底が変化する ? グラフラプラシアンは隣接行列で変化 ? 基底はグラフラプラシアンの固有ベクトル ? 学習するデータのグラフ構造が変化する ? 固有ベクトル（基底）が変化 ? 同じノード情報でも信号が変化 ? 学習が不安定になる 1畳み込み1次元分のノード情報しか畳み込めない ? チャネル方向の畳み込みが不可能 ? 1つのノード情報が n 次元 ? 畳み込みユニットを n 個用意する必要がある ? 計算量増大 Chevnetの問題点 24
- 25. 実験 ? ユークリッド構造のデータ ? MNIST ? 非ユークリッドのデータ ? 20NEWS Chevnetで行われていた実験 25
- 26. 実験 ? MNISTをグラフ化しグラフそのものを分類 ? ノード数 : 976(784(28×28)ピクセルと192個の偽ノード) ? 偽ノード ? pooling時にクラスタリングするノードがないときにグループ化させるためのノード ? 接続を持たない?フィルタ学習に影響しない ? エッジ数 : 3198 ? エッジはk-NNグラフ化(8-NN)で決められる ? 8-NNつまり注目ノードの最も近い8近傍が選ばれて接続される ? CNNと同じモデル構造でChevnetが近い精度を出した ユークリッド構造のデータでの実験 26 ドロップアウト : 0.5 正則化重み : 5*10-4 初期学習率 : 0.03 学習率減衰率 : 0.95 モーメンタム : 0.9 CNNフィルタ : 5*5 Chevnetフィルタ : K = 25 エポック数 : 20
- 27. 実験 ? データセット : 20NEWS Dataset（テキスト分類?クラスタリングに用いるデータセット） ? ノード数 : 10000 （word2vec埋め込み） ? エッジ数 : 132834 （ 16-NNで構築 ） （それぞれのクラスの文書特有のユニークワード1000語を抽出） ? 各文書 x は単語間で正規化された bag-of-words モデル ? モデル ： GC32 （ K = 5 , 1層 ） ? タスク ： テキスト分類（グラフ分類） ? 全結合よりはいい 非ユークリッド構造のデータでの実験 27 初期学習率 : 0.001 Chevnetフィルタ : K = 5 エポック数 : 20 最適化手法 : Adam
- 29. Chevnetの畳み込み ? 一回の畳み込みで注目ノードから k 近傍のノードを畳み込める ? ?(?) ? = ?=0 ??1 ? ?T? ( ?) T? ? = 2?T??1( ?) ? T??2( ?) T0 ? = 1, T1 ? = ? ①上式を?に対して線形に限定(? = 2)（ ? は非正規化ラプラシアン） ? ? ? ? = ?0T0 ? + ?1T1 (?) T0 ? = 1, T1 ? = ? ? ? ? ? = ?0 + ?1 ? ? GCNのConvolutionの導出 29
- 30. ①ChevNetのConvを?に対して線形に限定し単純化 ? ? ? ? = ?0 + ?1 ? ? = ?0 ? + ?1 ? ? ? ?? ? ? ??? ? ? ? ≈ ?0 ? ? ?1 ?? ? ? ??? ? ? ? ? 1層で注目ノードに対して 1 エッジ分の隣接ノードを畳み込み可能 ? 層を k 回重ねることで k エッジ分の隣接ノードを畳み込み可能 ? 学習可能なパラメータ ?0 , ?1 GCNのConvolutionの導出 30
- 31. ①ChevNetのConvを?に対して線形に限定し単純化 ? ? ? ? = ?0 + ?1 ? ? = ?0 ? + ?1 ? ? ? ?? ? ? ??? ? ? ? = ?0 ? + ?1 ? ? ?＋?1 ??? ? ? ??? ? ? ? ≈ ?0 ? ? ?1 ?? ? ? ??? ? ? ? GCNのConvolutionの導出 31 ? ? ?? ? ? ??? ? ? ?? = ??? = 1 ? 1 ???(? ?)???(? ?) 0 ? = ? ??? ???(??) ≠ 0 ? ≠ ? ??? ?? ?? ???????? ?? ?? ?????????
- 32. ChevNetのConvを?に対して線形に限定し単純化する ? = ? ? ? ? ≈ ?0 ? ? ?1 ?? ? ? ??? ? ? ? ②上式に対して ?0 = ??1 とパラメータ数を制限 ? ? ? ? ≈ ?0 ? ? ?1 ?? ? ? ??? ? ? ? ≈ ? ? ? + ?? ? ? ??? ? ? ? ? オーバーフィッティング対策 ? レイヤごとの演算（行列乗算など）を最小限に抑える GCNのConvolutionの導出 32 1つのノードの情報は1次元
- 33. ? ? ? ?? ? ? ??? ? ? と ? ? + ?? ? ? ??? ? ? の違い 33 ? + ?? ? ? ??? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? = ? ?. ? ?. ? ?. ? ? ? ?. ? ? ? ? ? ?? ? ? ??? ? ? ?? = ??? = 1 ? 1 ???(??)???(??) 0 ? = ? ??? ???(??) ≠ 0 ? ≠ ? ??? ?? ?? ???????? ?? ?? ????????? ? ? ?? ? ? ??? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = ? ??. ? ??. ? ??. ? ? ? ??. ? ? ? 0 1 2 0 0 1 1 1 1 0 0 2 1 0 0 隣接行列 A ? + ?? ? ? ??? ? ? ?? = ??? = 1 1 ???(??)???(??) 0 ? = ? ??? ???(??) ≠ 0 ? ≠ ? ??? ?? ?? ???????? ?? ?? ????????? 0 1 2 正規化ラプラシアンとほぼ同じ
- 34. ? ? ? ? ≈ ? ? ? + ?? ? ? ??? ? ? ? ? ? ? + ?? ? ? ??? ? ? は 0 ≤ ? ??? ≤ 2 の最大固有値を持つ ? ? ? + ?? ? ? ??? ? ? を繰り返すと数値的に不安定になる ? 勾配爆発/消失につながる ? ”renormalization trick” を使用して軽減させる ? ? + ?? ? ? ??? ? ? → ?? ? ? ? ?? ? ? ? = ? + ? ? ? = ? ??? GCNのConvolutionの導出 34
- 35. ③GCN ? = ??Θ = ?? ? ? ? ?? ? ? ?Θ ? Θ をフィルタ行列とする ? 1つのノードのノード情報が多次元情報でも1回の計算で畳み込み可能 GCNのConvolutionの導出 35
- 36. GCNのConvolutionについて 次の例で考える 0 1 2 0 0 1 1 1 1 0 0 2 1 0 0 隣接行列 A 0 1 2
- 37. GCNのConvolutionについて 37 ?? ? ? ? ?? ? ? ?? = 1 ??? ? ? +1 ???(? ?)+1) 1 ??? ? ? +1 ???(? ?)+1) 0 ? = ? ??? ???(??) ≠ 0 ? ≠ ? ??? ?? ?? ???????? ?? ?? ????????? ?? ? ? ? ?? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = ?. ? ?. ? ?. ? ?. ? ?. ? ? ?. ? ? ?. ? 0 1 2 0 0 1 1 1 1 0 0 2 1 0 0 隣接行列 A ? ?? ? ? ? ?? ? ? のそれぞの要素は 2つのノードの関係（エッジ）の関係を 表している ? 注目ノードと隣接ノードの接続数が多い ? ?? ? ? ? ?? ? ? の要素値は小さい値をとる ? 注目ノードと隣接ノードの接続数が少ない ? ?? ? ? ? ?? ? ? の要素値は大きい値をとる ? つまり，注目ノードと隣接ノード数が少ない ノード情報を重視する
- 38. GCNのConvolutionについて 38 ?? ? ? ? ?? ? ? ?? = 1 ??? ? ? +1 ???(? ?)+1) 1 ??? ? ? +1 ???(? ?)+1) 0 ? = ? ??? ???(??) ≠ 0 ? ≠ ? ??? ?? ?? ???????? ?? ?? ????????? ?? ? ? ? ?? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = ?. ? ?. ? ?. ? ?. ? ?. ? ? ?. ? ? ?. ? ? ? ?? ? ? ??? ? ? ?? = ??? = 1 ? 1 ???(??)???(??) 0 ? = ? ??? ???(??) ≠ 0 ? ≠ ? ??? ?? ?? ???????? ?? ?? ????????? ? ? ?? ? ? ??? ? ? = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? = ? ??. ? ??. ? ??. ? ? ? ??. ? ? ? 0 1 2 0 0 1 1 1 1 0 0 2 1 0 0 隣接行列 Aを下のように定義した時の ?? ? ? ? ?? ? ?と正規化ラプラシアンの比較 隣接行列 A
- 39. GCNのConvolutionについて ?? ? ? ? ?? ? ? ? は自己ノードとその隣接ノード情報を集める ? 橙枠の計算を行うとき、 ? 自己ノード ： 1 ??? ? ? +1 deg(? ?) +1) × 自己ノード情報 ? 隣接ノード ： 1 ??? ? ? +1 ???(? ?) +1) × 隣接ノード情報 ? 接続していないノード ： 0 × ノード情報 ?? ? ? ? ?? ? ? ? = ?. ? ?. ? ?. ? ?. ? ?. ? ? ?. ? ? ?. ? ? ? ? ? ? ? = ?. ? ?. ? ? ?. ? ?. ? ?. ? 39 0 1 2 注目ノードと隣接ノードの関係を表す正規化定数（エッジ重み）
- 40. ?? ? ? ? ?? ? ? ?? = ?. ? ?. ? ? ?. ? ?. ? ?. ? ? ? ? ? ? ? ? ? ? ? = ?? ?? ?? ?? ?? ?. ? ??. ? ??. ? ??. ? ??. ? ?. ? ??. ? ??. ? ??. ? ??. ? 1 2 3 4 5 1 2 3 4 5 ←畳み込む前のノードのチャネル ↑畳み込み後のノードのチャネル GCNのConvolutionについて ? ?? ? ? ? ?? ? ? ?は自己ノードとその隣接ノード情報を集めた値だった ? その値に対して重みをかけて計算した結果が畳み込み処理後の値となる ? 空間的な畳み込みに近い 重み ? 畳み込み後のノード３のノード情報↑↑重み?↑ ?? ? ? ? ?? ? ? ? 0 1 2 40
- 41. ?? ? ? ? ?? ? ?が固定値 ? 注目ノードに対するそれぞれの隣接ノードが必要不必要関係なく統合されてしまう ?注目ノードと隣接ノードの値から求められるようにパラメータ化できれば理想 空間方向の局所的な畳み込みができていない ? 畳み込み演算を行うときに ?? ? ? ? ?? ? ? ? で注目?隣接ノード情報を集めてしまう ? それぞれのノードに対して重みをかけられない チャネルの方向および空間方向の畳み込むにしてはパラメータが少ない ? CNNに使用するConvolution だと畳み込みフィルタがチャネルごとに分かれている ? GCNのほうはConvolution前のチャネル数× Convolutionあとのチャネル数しかない ? 著者曰く画像のようなデータに対してはモデルが貧弱 GCNのGraph Convolutionの問題点 41
- 43. データセット ? 文書引用ネットワークのデータセット ： Citeseer, Cora, Pubmed ? ノード ： 文書データ ? エッジ ： 引用リンク（文書 I が文書 j を引用した場合2つのエッジは1（接続）） ? ノードのクラス ＝ 文書の内容別クラス GCNで行われていた実験 43
- 44. データセット ? 知識グラフのデータセット ： NELL ? ノード ： 単語（ベクトル表現） ? エッジ ： 関係 ? ノードのクラス例 ? Tront, Canada : country GCNで行われていた実験 44
- 45. GCNで行われていた実験 45 ? GCNモデル構造 ： GCN2層 ? = ? ?, ? = ??????? ? ???? ???(0) ?(1)
- 46. GCNで行われていた実験 46
Editor's Notes
- #3: ノードの情報は 行ごとに入っている
- #5: グラフラプラシアンというグラフの構造に依存した行列の固有値固有ベクトルを用いてフーリエ変換を行う 固有値 λ ? ：グラフ周波数 固有ベクトル ? λ ? ：フーリエ基底 になってます グラフのノード情報のベクトルに対して基底ベクトルとの内積をとることでその周波数成分が取り出せる 後でフーリエ変換で使用するので説明しておく ーーーーーーーーーーーーーーーーーーーー 基底とは 与えられたベクトル空間の全てのベクトルを表すことができるものを言う ベクトル空間に基底が与えられれば、その空間の元は必ず基底ベクトルの線型結合としてただ一通りに表すことができる ーーーーーーーーーーーーーーーーーーーーーーー 固有値（グラフ周波数）が 大きい?固有ベクトルは激しく振動 小さい?固有ベクトルは緩やかに振動
- #6: 後でフーリエ変換で使用するので説明しておく フーリエ変換とラプラシアンの関係があるように グラフフーリエ変换もグラフラプラシアンと関係がありますが その関係はまだ理解できていません ここではフーリエ変換するためにグラフラプラシアンを使用するという理解でもいいと思います ーーーーーーーーーーーーーーーーーーーーーー 個人的に正規化することでフィルタリングがしやすくなるのではないか
- #7: 逆フーリエ変换后のノード办の情报
- #8: 逆フーリエ変换后のノード办の情报 N：ノード数
- #9: 逆フーリエ変换后のノード办の情报
- #10: ?λにおける応答が 通常の周波数特性に対応する
- #16: オレンジの部分はラプラシン行列尝のｐ乗になる
- #17: オレンジの部分はラプラシン行列尝のｐ乗になる
- #18: Kの数は近似したλ多項式の数と一致 Kは複数ある
- #19: フィルタ ? ?? は行列Lが定数なのでフィルタ係数はαpであり、この操作で注目ノードにと注目ノードからpステップで行けるノードをまとめてフィルタリング処理をする スペクトル上での畳み込みは左側での式のαpを学習させればいいじゃんという考えでできたもの スペクトル上でのグラフコンボリューションはこれが始まりのきっかけ
- #20: 改めて肠丑别惫苍别迟に注目
- #21: 漸化式 T ? ? = 2?T ??1 ( ? ) - T ??2 ( ? )
- #22: Chevnetはスペクトル上での畳み込みで問題だった計算量の増大をチェビシェフの多項式にすることで抑えた 漸化式 T ? ? = 2?T ??1 ( ? ) - T ??2 ( ? ) この近似はグラフ信号処理でよく行われている Cosnθはcosθのn次多項式式で近似可能 そのn次多項式は漸化式 Tn(x) を満たす
- #23: 理由はあとで
- #24: チェビシェフにしても グラフラプラシアンを使用しているので 固有値固有ベクトル関係してますよ
- #25: 固有値を-1 ~ 1 にしてできるだけ変化しないように抑えているが
- #28: 各文書xは単語間で正規化されたbag-of-wordsモデル 我々のモデルをテストするために用いて16-NNグラフを構築 各単語の意味をベクトル表現化する手法
- #29: 最も使用率の高いGraphConvolution これを改善したとかエンコーダデコーダモデルを作ったりといろいろ利用されていることが多い
- #30: 碍＝２はシグマの碍-1のところの碍
- #31: 余因子行列 ?
- #32: ?? ? ? ? ? ? ? ? ? ? から ? ? ? ? ? ? ? ? ? への単純化は Θ0でのところに I はあるからそれほど変化しない ? ? 0 ?+ ? 1 ? ? ?＋ ? 1 ? ? ? ? ? ? ? ? ? ? ? ? 0 ?と ? 1 ? ? ?を ? 0 ?にまとめた
- #33: 正規化ラプラシアンのすべてに要素に同じ重み ? 0 をかける すべての要素に同じ重み ? 1 を加える
- #34: ?? ? ? ? ? ? ? ? ? ? は正規化ラプラシアン ?+ ? ? ? ? ? ? ? ? ? は正規化ラプラシアンの要素が同じですべて正
- #35: ここはよくわからない
- #36: 余因子行列 ?
- #37: 別の見方で説明する 計算に注目してみる
- #38: 骋颁狈はは同じエポック数で约72秒
- #39: 0の位置以外はほぼ違う スペクトルと空間の中間のような状態
- #40: 骋颁狈はは同じエポック数で约72秒
- #41: 骋颁狈はは同じエポック数で约72秒
- #42: 固有値を-1 ~ 1 にしてできるだけ変化しないように抑えているが複数のGCNレイヤを積み重ねると、過度に平滑化されます。つまり、すべての頂点が同じ値に収束します。
- #43: 固有値を-1 ~ 1
- #44: 隣接ノードが似たような特徴を持っているので 2層でいい 文書データ:bag of words 引用ネットワークデータセットでは、 Coraのみでハイパーパラメータを最適化 CiteseerとPubmedに対して同じパラメータセットを使用します。 Adam 学習率0.01 ウィンドウサイズ10で早期停止 (例:検証の損失が10の連続したエポックで減少しなければ、トレーニングを中止します。) 最大200エポック（トレーニング反復）のすべてのモデルを訓練 Glorot＆Bengio（2010）で説明した初期化を使用して重みを初期化 それに応じて（行）正規化入力フィーチャベクトルを使用 Citeseer, Cora, Pubmed 0.5（ドロップアウト率） L2正則化 16（隠れ層のチャネル数） NELL 0.1（ドロップアウト率） L2正則化 64（隠れ層のチャネル数）
- #45: もともとこのようなグラフがある ノードには単語 エッジには例えばトヨタとGMがライバル関係にある とか Skydomeはカナダのcitystadiumだよみたいな感じで 意味情報を使用せずその接続だけを利用する データセットの中にノードのクラスデータが入っているのでそれでノード分類を学習する 例えばトロントとカナダはカントリークラスのようなかんじで
- #46: 余因子行列 ?
- #47: データセットが似たようなノードが接続されているので 2層つまり2エッジ分しか畳み込まなくてもいいような気がする ノードクラスタリングはグラフそのものを識別するよりも問題が簡単