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

2024年度前期輪読会#8 グラフィカルニューラルネットワーク6.4 物理工学科卒 上野 裕太 0

6章前半の復習 グラフフーリエ変換 グラフ𝐺𝐺 = 𝑉𝑉, 𝐸𝐸 上の信号𝒇𝒇 ∈ ℝ 𝑉𝑉 をグラフフーリエ基底 𝒉𝒉𝑖𝑖 𝑖𝑖 に対する周波数成分 𝛼𝛼𝑖𝑖 𝑖𝑖 に変換する 𝒇𝒇 ↦ 𝜶𝜶 = 𝛼𝛼1 , 𝛼𝛼2 , … , 𝛼𝛼 𝑉𝑉 𝜶𝜶 = 𝑯𝑯T 𝒇𝒇, T s. t. 𝑯𝑯 = 𝒉𝒉1 𝒉𝒉2 … 𝒉𝒉 𝑉𝑉 グラフフーリエ基底を求めるために解くべき問題 𝑛𝑛 𝒇𝒇 = � 𝛼𝛼𝑖𝑖 𝒉𝒉𝑖𝑖 𝑖𝑖=1 ∈ ℝ 𝑉𝑉 × 𝑉𝑉 𝑘𝑘番目のグラフフーリエ基底𝒉𝒉𝑘𝑘 ∈ ℝ 𝑉𝑉 は、それまでの基底と直交するものの中で ディリクレエネルギーVar 𝒇𝒇 が最小なものである 𝒉𝒉𝑘𝑘 = Minimize Var 𝒇𝒇 𝒇𝒇∈ℝ 𝑉𝑉 解法 s. t. 𝒇𝒇 2 = 1, Var 𝒇𝒇 ≝ � 𝑢𝑢,𝑣𝑣 ∈𝐸𝐸 𝒇𝒇T 𝒉𝒉𝑖𝑖 = 0, 𝒇𝒇 𝑢𝑢 − 𝒇𝒇 𝑣𝑣 2 𝑖𝑖 = 1, … , 𝑘𝑘 − 1 グラフラプラシアン𝑳𝑳 = 𝑫𝑫 − 𝑨𝑨の固有値と固有ベクトルを求め、固有値の小さい順に基底をとる 𝑳𝑳 = 𝑯𝑯𝚲𝚲𝑯𝑯T , 𝑳𝑳𝒉𝒉𝑖𝑖 = 𝜆𝜆𝑖𝑖 𝒉𝒉𝒊𝒊 , 𝚲𝚲 = diag 𝜆𝜆1 , 𝜆𝜆2 , … , 𝜆𝜆 𝑉𝑉 , 𝜆𝜆1 ≤ 𝜆𝜆2 ≤ ⋯ ≤ 𝜆𝜆 𝑉𝑉 1

6.4.1 スペクトルを変調するモデル 以下のような問題を解くことを考える 問題6.4（固定グラフ上の信号の変換と訓練） グラフ𝐺𝐺を固定する．訓練時には，𝐺𝐺上の入力信号𝒙𝒙𝑖𝑖 ∈ ℝ𝑛𝑛 と教師信号𝒚𝒚𝑖𝑖 ∈ ℝ𝑛𝑛 の対 𝒙𝒙𝑖𝑖 , 𝒚𝒚𝑖𝑖 𝑖𝑖 が与 えられます．テスト時に，新しい入力信号𝒙𝒙が与えられたときに，𝒙𝒙 ∈ ℝ𝑛𝑛 に対する出力信号𝑦𝑦 ∈ ℝ𝑛𝑛 を予測することが目標です． 例）𝐺𝐺は交通ネットワーク，𝒙𝒙𝑖𝑖 は𝑖𝑖日目の朝の交通量，𝒚𝒚𝑖𝑖 は𝑖𝑖日目の夜の交通量 これを以下のようなパラメータ𝜽𝜽のモデルとして学習する 𝜶𝜶 = 𝑯𝑯T 𝒙𝒙 周波数成分に変換 � = 𝑯𝑯𝑯𝑯 𝒚𝒚 信号に復元 𝜷𝜷 = 𝜽𝜽 ⊙ 𝜶𝜶 ここで𝜽𝜽 ⊙ 𝜶𝜶は要素ごとの積を取る 周波数成分を変調 2

6.4.1 スペクトルを変調するモデル グラフの畳み込み 先のモデル� 𝒚𝒚を𝑯𝑯𝑯𝑯と𝒙𝒙を畳み込んだものとして、グラフに対する畳み込みを定義する これは以下の一般的なフーリエ変換における畳み込みの性質に基づく 性質 ̂ 𝑔𝑔とする．このとき畳み込み𝑓𝑓 信号𝑓𝑓, 𝑔𝑔の周波数成分をそれぞれ𝑓𝑓, � ∗ 𝑔𝑔の周波数成分は𝑓𝑓̂ 𝑔𝑔である． � 連続空間 信号𝑓𝑓 信号𝑔𝑔 ∗ 信号𝑓𝑓 ∗ 𝑔𝑔 ℱ ℱ ℱ 𝑓𝑓 ∗ 𝑔𝑔 𝑡𝑡 = � 𝑓𝑓 𝜏𝜏 𝑔𝑔 𝑡𝑡 − 𝜏𝜏 𝑑𝑑𝑑𝑑 頂点空間 周波数成分𝑓𝑓̂ 周波数成分𝑔𝑔� × 周波数成分𝑓𝑓̂ 𝑔𝑔� 信号𝑯𝑯𝑯𝑯 信号𝒙𝒙 ∗ 信号𝑯𝑯𝑯𝑯 ∗ 𝒙𝒙 𝑯𝑯T 𝑯𝑯T 𝑯𝑯T 周波数成分𝜽𝜽 周波数成分𝜶𝜶 ⊙ 周波数成分𝜽𝜽 ⊙ 𝜶𝜶 3

6.4.1 スペクトルを変調するモデル 多次元の入出力の場合 入力特徴が𝑑𝑑in 種類 出力特徴が𝑑𝑑out 種類 入力信号𝑿𝑿 ∈ ℝ𝑛𝑛×𝑑𝑑in 出力信号𝒀𝒀 ∈ ℝ𝑛𝑛×𝑑𝑑out 𝜶𝜶 = 𝑯𝑯T 𝑿𝑿 ∈ ℝ𝑛𝑛×𝑑𝑑in 𝜷𝜷𝑗𝑗 = � 𝜽𝜽𝑖𝑖𝑖𝑖 ⨀𝜶𝜶:,𝑖𝑖 , 𝑖𝑖 𝜽𝜽𝑖𝑖𝑖𝑖 ∈ ℝ𝑛𝑛 � = 𝑯𝑯𝑯𝑯 ∈ ℝ𝑛𝑛×𝑑𝑑out 𝒀𝒀 4

6.4.1 スペクトルを変調するモデル どの周波数成分を強調する？ 同類選好的なグラフ→低周波数成分を強調する 異類選好的なグラフ→中周波数成分を強調する 5

6.4.2 変調を固有値の関数で表現する 変調を固有値の関数としてモデル化 𝜶𝜶 = 𝑯𝑯T 𝒙𝒙 𝑛𝑛 𝜷𝜷 = � 𝑓𝑓𝜽𝜽 𝝀𝝀 𝜶𝜶𝑖𝑖 𝑖𝑖=1 � = 𝑯𝑯𝑯𝑯 𝒚𝒚 関数のモデル化の例（多項式モデル） 𝑓𝑓𝜽𝜽 𝜆𝜆 = 𝜃𝜃0 + 𝜃𝜃1 𝜆𝜆 + ⋯ + 𝜃𝜃𝑘𝑘 𝜆𝜆𝑘𝑘 動機 ● 6.4.1ではパラメータ間の関係が完全に独立 ● 良いモデルとは？→グラフの形が少し変わるとパラメータも少しだけ変化 ● 固有値の値が近いもの同士はパラメータも近くなって欲しい 6

6.4.3 局所的なフィルタ 多項式モデルを用いた場合の計算量の削減 教科書p181~182の計算を経て， 𝑘𝑘 � = 𝜃𝜃0 𝒙𝒙 + � 𝜃𝜃𝑖𝑖 𝑳𝑳𝑖𝑖 𝒙𝒙 𝒚𝒚 𝑖𝑖=1 𝑯𝑯が消える 𝐿𝐿は非ゼロ成分が 𝑉𝑉 + 2 𝐸𝐸 個のみの疎行列→行列の積の計算量は𝑂𝑂 𝑉𝑉 + 𝐸𝐸 全体で𝑂𝑂 𝑘𝑘 𝑉𝑉 + 𝐸𝐸 𝐻𝐻は密行列なので𝑂𝑂 𝑉𝑉 2 かかる このモデルは頂点𝑣𝑣における出力信号が頂点𝑣𝑣から𝑘𝑘ホップ以内の頂点集合の入力信号のみで求まる → 帰納法により証明可能（教科書p.183） 画像における畳み込みと局所性の共通点が見えてくる 7

6.4.4 ChebNet 固有値関数𝑓𝑓𝜽𝜽 𝜆𝜆 の基底としてチェビシェフ多項式を用いる 𝑇𝑇0 𝑥𝑥 = 1 𝑇𝑇1 𝑥𝑥 = 𝑥𝑥 𝑇𝑇𝑖𝑖+1 𝑥𝑥 = 2𝑥𝑥𝑇𝑇𝑖𝑖 𝑥𝑥 − 𝑇𝑇𝑖𝑖−1 𝑥𝑥 チェビシェフ多項式は[−1,1]上の関数の直交基底である [−1,1]上の内積の定義 𝑓𝑓, 𝑔𝑔 ≝ � 1 −1 𝑓𝑓 𝑥𝑥 𝑔𝑔 𝑥𝑥 1 − 𝑥𝑥 2 𝑑𝑑𝑑𝑑 ここでグラフラプラシアン𝑳𝑳の固有値が[−1,1]におさまるように正規化 2 � 𝑳𝑳 = 𝑳𝑳 − 𝑰𝑰 𝜆𝜆𝑛𝑛 任意の固有値関数𝑓𝑓𝜽𝜽 𝜆𝜆 : −1,1 → ℝを𝑘𝑘次のチェビシェフ多項式で近似 𝑘𝑘 𝑓𝑓𝜽𝜽 𝜆𝜆 = � 𝜃𝜃𝑖𝑖 𝑇𝑇𝑖𝑖 𝜆𝜆 𝑖𝑖=0 8

6.4.4 ChebNet 6.4.3と同様に計算すると畳み込みは以下で表される 𝑘𝑘 � = 𝜃𝜃0 𝒙𝒙 + � 𝜃𝜃𝑖𝑖 𝑇𝑇𝑖𝑖 � 𝒚𝒚 𝑳𝑳 𝒙𝒙 多項式の場合と同様に 𝑖𝑖=1 ● 計算量𝑂𝑂 𝑘𝑘 𝑉𝑉 + 𝐸𝐸 ● 頂点𝑣𝑣の出力信号は頂点𝑣𝑣から𝑘𝑘ホップ以内の頂点集合の入力信号のみに依存する 多項式の場合と比べて ● 基底が直交しているので各パラメータが小さい値になりやすい ただチェビシェフ多項式の方が多項式より明らかに優れているかと言うとそうでもない 9

6.4.5 正規化ラプラシアン 多項式モデル 𝑘𝑘 � = 𝜃𝜃0 𝒙𝒙 + � 𝜃𝜃𝑖𝑖 𝑳𝑳𝑖𝑖 𝒙𝒙 𝒚𝒚 対称正規化ラプラシアン ● 固有値が[0,2]に収まる ● 固有ベクトルが直交 推移ラプラシアン 固有値が大きいと巨大に！ 固有値を抑えたい！ 𝑖𝑖=1 1 1 1 1 − − − − sym 𝑳𝑳 ≝ 𝑫𝑫 2 𝑳𝑳𝑫𝑫 2 = 𝑰𝑰 − 𝑫𝑫 2 𝑨𝑨𝑫𝑫 2 𝐿𝐿rw ≝ 𝑫𝑫−1 𝑳𝑳 = 𝑰𝑰 − 𝑫𝑫−1 𝑨𝑨 ● 固有値集合が対称正規化ラプラシアンと等しい ● 対称正規化ラプラシアンが固有値𝜆𝜆，固有ベクトル𝒉𝒉を持つとき、推移ラプラシアンは固有値𝜆𝜆， 1 −2 固有ベクトル𝑫𝑫 𝒉𝒉を持つ ● 固有ベクトルは直交しない 10

6.4.5 正規化ラプラシアン 対称正規化ラプラシアンへの置き換え ディリクレエネルギーの置き換え Var sym 𝒇𝒇 ≝ 𝒇𝒇T 𝑳𝑳sym 𝒇𝒇 = 最適化問題 sym 𝒉𝒉𝑘𝑘 = Minimize Var sym 𝒇𝒇 𝒇𝒇∈ℝ 𝑉𝑉 s. t. � 𝑢𝑢,𝑣𝑣 ∈𝐸𝐸 𝑓𝑓 𝑢𝑢 deg 𝑢𝑢 𝑓𝑓 𝑣𝑣 − deg 𝑣𝑣 sym 𝒇𝒇T 𝒉𝒉𝑖𝑖 𝒇𝒇 2 = 1, = 0, 2 𝑖𝑖 = 1, … , 𝑘𝑘 − 1 最適化問題の解 sym 𝑳𝑳sym の固有ベクトルを固有値の小さい順に並べた𝒉𝒉1 sym , 𝒉𝒉2 sym , … , 𝒉𝒉𝑛𝑛 が解 11

6.4.6 グラフ畳み込みネットワーク 3.2.1節のグラフ畳み込みネットワークはスペクトルモデルの特別な場合と言える 1次の多項式のモデル 𝜃𝜃 = 𝜃𝜃0 + 𝜃𝜃1 = −𝜃𝜃1 という制約を与える − � = 𝜃𝜃 𝑰𝑰𝑛𝑛 + 𝑫𝑫 𝒚𝒚 1 1 − 2 𝑨𝑨𝑫𝑫 2 𝒙𝒙, 自己ループを持つグラフとして考える � = 𝜃𝜃0 𝒙𝒙 + 𝜃𝜃1 𝑳𝑳sym 𝒙𝒙 𝒚𝒚 �𝑣𝑣 = 𝜽𝜽 𝒙𝒙𝑣𝑣 + � 𝒚𝒚 𝑢𝑢∈𝒩𝒩 𝑣𝑣 �− � = 𝜃𝜃 𝑫𝑫 𝒚𝒚 1 deg 𝑢𝑢 deg 𝑣𝑣 𝒙𝒙𝑢𝑢 1 1 − � 𝑫𝑫 � 2 𝒙𝒙 2 𝑨𝑨 入力次元𝑑𝑑in ，出力次元𝑑𝑑out としてパラメータを𝜃𝜃から𝑾𝑾 ∈ ℝ𝑑𝑑in×𝑑𝑑out に 活性化関数𝜎𝜎 � = 1の場合と等しい �− � = 𝑫𝑫 𝒀𝒀 1 1 − � 𝑫𝑫 � 2 𝑿𝑿𝑿𝑿 2 𝑨𝑨 12

6.4.6 グラフ畳み込みネットワーク メッセージ伝達型グラフニューラルネットワークをスペクトル変調として解釈できる 集約の例 教科書のp75を参考にして、隣接頂点と自分自身を集約する場合、以下のようになる なお𝑯𝑯は各頂点の中間表現𝒉𝒉𝑖𝑖 ∈ ℝ𝑛𝑛 を並べたもの 𝑯𝑯 𝑙𝑙+1 − = 𝑰𝑰𝑛𝑛 + 𝑫𝑫 1 1 − 2 𝑨𝑨𝑫𝑫 2 𝑯𝑯 𝑙𝑙 = 2𝑰𝑰𝑛𝑛 − 𝑳𝑳sym 𝒙𝒙 これは𝑓𝑓 𝜆𝜆 = 2 − 𝜆𝜆のフィルタで変調することと等価 つまり、 ● 低周波を強調 ● 高周波をカット 13

14