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

2024前期輪読会＃6 グラフィカルニューラルネットワーク6.3 京都大学 工学部 宮前 明生 0

目次 1 グラフ上の信号 2 グラフフーリエ基底 3 ソフトなカットとしての解釈 4 固有値からグラフを推定 5 グラフフーリエ変換 1

グラフ上の信号 グラフ上の信号を𝒇 ∈ 𝑅𝑉 と表す。(𝑣)は頂点𝑣 ∈ 𝑉の信号 𝑓 𝑣1 𝒇 = 𝑓 𝑣2 ( 𝑉 = 3のとき) 𝑓 𝑣3 信号は、頂点のある特徴かクラスラベルを表す場合がある。 ただし、クラスラベルはワンホットベクトルで表す。 ワンホットベクトルとは、dクラスあるとすると𝑓𝑖 𝑣 (𝑖 = 1,2, … , 𝑑)が 𝑖クラスに属するならば１、属さないならば0として、 d個のベクトル𝑓1 𝑣 , 𝑓2 𝑣 , … , 𝑓𝑑 𝑣 でクラスを表す。 𝑉 = 3のとき標準基底𝒆1 , 𝒆2 , 𝒆3 を用いて𝒇を表すと、 𝑓 𝑣1 𝒇 = 𝑓 𝑣2 𝑓 𝑣3 = 𝑓 𝑣1 1 0 + 𝑓 𝑣2 0 0 1 + 𝑓 𝑣3 0 0 0 = 𝑓 𝑣1 𝒆1 + 𝑓 𝑣1 𝒆1 + 𝑓 𝑣1 𝒆1 1 2

グラフフーリエ基底 グラフフーリエ基底とは グラフ上の信号をグラフ間の変化が少ない低周波成分と変化が大きい高周波成分 に分割する。グラフ上の信号をグラフ間の変化が少ない基底と変化が大きい基底 で表す。 低周波の基底 高周波の基底 （黒いほど信号が大きい） グラフ中の変化度合いを隣接する頂点の信号の差の二乗和で定義する。 𝑉𝑎𝑟 𝒇 = ෍ (𝑓 𝑢 − 𝑓(𝑣))2 = 𝒇𝑇 𝑳𝒇 𝑢,𝑣 ∈𝐸 𝑳 = 𝐀 − 𝐃と定義する。 𝐀は隣接行列、 𝐃は頂点の次数を対角成分に並べた行列 𝑳はグラフラプラシアンまたはラプラシアンという。 𝑉𝑎𝑟 𝑓 を用いて、変化量が異なる直行基底を求める。 3

グラフフーリエ基底 まず、グラフ中の変化が最も少ない基底を求める。 2 minimaze 𝑉𝑎𝑟 𝒇 𝑠. 𝑡. 𝒇 =1 𝑉 これは定数関数𝒉1 = 𝒇∈ℝ 1 𝑛 𝑉𝑎𝑟 𝒉1 = σ 𝑢,𝑣 ∈𝐸( 1 1 − )2 = 0（ 𝑉𝑎𝑟 𝒇 𝑛 𝑛 ≥ 0） 次に変化の少ない基底𝒉2 は 2 = 1, 𝒇𝑇 𝒉 = 0 minimize 𝑉𝑎𝑟 𝒇 𝑠. 𝑡. 𝒇 1 𝑉 𝑓∈ℝ 同様に𝒉3 , 𝒉4 , … , 𝒉𝑛 と求める。 𝒉𝑛 を求めるには、以下の最適化問題を解く。 2 = 1, 𝒇𝑇 𝒉 = 0 (𝑖 = 1,2, … , 𝑘 − 1) minimize 𝑉𝑎𝑟 𝒇 𝑠. 𝑡. 𝒇 𝑖 𝑉 𝑓∈ℝ この解は、ラプラシアン𝑳の正規直行固有ベクトルを固有値の小さい順に並べた 𝒉1 , 𝒉2 , … , 𝒉𝑛 となる。 ラプラシアンの固有値の列𝜆1 , 𝜆2 , … , 𝜆𝑛 をグラフスペクトルまたはスペクトル 正規直行固有ベクトル𝒉1 , 𝒉2 , … , 𝒉𝑛 グラフフーリエ基底と呼ぶ。 4

グラフフーリエ基底 固有値、固有ベクトルとは 𝑛 × 𝑛の正方行列𝐀に対して、 𝐀𝒙 = 𝜆𝒙 これらを満たす𝒙 ∈ ℝ𝑛 , 𝜆 ∈ ℝが存在するとき 𝐱を固有ベクトル、𝜆を固有値と呼ぶ。 ラグランジュの未定乗数法とは 制限付きの極値を求める手法。 極値が最小値の場合、 minimize 𝑓 𝒙 𝑠. 𝑡. 𝑔 𝒙 = 0 𝑛 𝑓 𝒙 𝒙 ∈ℝ 𝜕𝑔 𝜕𝒙 𝑔 𝒙 =0 これは、以下の最適化問題を解くと求められる minimize 𝐿 𝒙, 𝜆 (𝐿 𝒙, 𝜆 = 𝑓 𝒙 − 𝜆𝑔 𝒙 ) 𝑛 𝒙 ∈ℝ ,𝜆∈ℝ 𝜕𝐿 𝜕𝐿 この解は = = 0を満たす。 𝜕𝒙 𝜕𝜆 𝜕𝐿 𝜕𝐿 𝜕𝑓 𝜕𝑔 = =0⟺ =𝜆 ,𝑔 𝒙 = 0 𝜕𝒙 𝜕𝜆 𝜕𝒙 𝜕𝒙 𝜕𝑓 𝜕𝒙 5

グラフフーリエ基底 ラグランジュの未定乗数法を用いたグラフフーリエ基底が固有ベクトルになる証明 グラフ中の変化が最も少ない基底を求める最適化問題は、 𝑇 𝑳𝒇 𝑠. 𝑡. 𝒇 2 = 1(𝒇𝑇 𝒇 = 1) minimaze 𝒇 𝑉 𝒇∈ℝ ラグランジュの未定乗数法で極値を求める。 𝐿 𝒇, 𝜆 = 𝒇𝑇 𝑳𝒇 − 𝜆(𝒇𝑇 𝒇 − 1) 𝜕𝐿 = 𝑳𝒇 − 𝜆𝒇 = 0 𝜕𝒇 𝑳𝒇 = 𝜆𝒇 よって、𝒇, 𝜆はそれぞれ𝑳に対する固有ベクトル、固有値（ただし𝒇𝑇 𝒇 = 1 ） ある固有ベクトルを𝒇𝑖 、固有値を𝜆𝑖 とすると、極値は 𝑉𝑎𝑟 𝒇𝑖 = 𝒇𝑖 𝑇 𝑳𝒇𝑖 = 𝒇𝑖 𝑇 𝜆𝑖 𝒇𝑖 = 𝜆𝑖 𝒇𝑖 𝑇 𝒇𝑖 = 𝜆𝑖 固有値を小さい順に𝜆1 , 𝜆2 , … , 𝜆𝑛 とすると、 𝑉𝑎𝑟 𝒇1 が最小、 𝑉𝑎𝑟 𝒇𝑛 が最大 あとは、 𝒇𝑖 𝑇 𝒇𝑗 = 0(𝑖, 𝑗 = 1,2, … , 𝑛, 𝑖 ≠ 𝑗)を満たすように直行化する。 6

グラフフーリエ基底 その他の解が固有ベクトルになる例 主成分分析 高次元のデータを低次元に圧縮する。（単語ベクトルを可視化） データ𝒙𝑛 (𝑛 = 1, … , 𝑁)に一次元への射影𝒉𝟏 を考える。（ただし𝒉𝟏 𝑇 𝒉𝟏 = 1 ） 𝒉𝟏 で射影するとスカラー値𝒉𝟏 𝑇 𝒙𝑛 1 ഥは平均値、ഥ 射影されたデータの分散が最大になる𝒉𝟏 を求める。 𝒙 𝒙 = σ𝑁 𝑛=1 𝒙𝑛 𝑁 𝑁 𝑛=1 𝑛=1 𝑁 1 1 𝑇 𝑇 2 ഥ) = ෍ 𝒉𝟏 𝑇 (𝒙𝑛 − 𝒙 ഥ) (𝒙𝑛 − 𝒙 ഥ)𝑇 𝒉𝟏 = 𝒉𝟏 𝑇 𝑺𝒉𝟏 ෍ (𝒖𝟏 𝒙𝑛 − 𝒖𝟏 𝒙 𝑁 𝑁 𝒙𝟐 𝑁 1 ഥ) (𝒙𝑛 − 𝒙 ഥ )𝑇 𝑺 = ෍ (𝒙𝑛 − 𝒙 𝑁 データ𝒙𝑛 𝒉𝟏 𝒉𝟏 𝑇 𝒙𝑛 𝒙𝟏 𝑛=1 グラフ中の変化が最も少ない基底を求める最適化問題と同じ 𝑇 𝑳𝒇 𝑠. 𝑡. 𝒇𝑇 𝒇 = 1 minimaze 𝒇 𝑉 𝒇∈ℝ 7

ソフトなカットとしての解釈 最小カット問題とは 頂点𝑽を分割して得られる２つの頂点集合𝑺と𝑻の中で、 𝑺と𝑻の間の辺の本数が最 小になるものを求める。 最小カット問題と𝑉𝑎𝑟 𝒇 の最小化問題の関係 𝑺 𝑻 グラフフーリエ基底の定数関数𝒉1 が存在し、𝒇𝑇 𝒉1 = 0 を満たすならば、𝒇には正の成分と負の成分がある。 粗く考えて、 𝒇は-１か１を成分にとるとする。 𝑉𝑎𝑟 𝒇 = ෍ (𝑓 𝑢 − 𝑓(𝑣))2 = ෍ 1[𝑢 ∈ 𝑺]1[𝑣 ∈ 𝑻](𝑓 𝑢 − 𝑓(𝑣))2 𝑢,𝑣 ∈𝐸 =4 ෍ 1𝑢∈𝑺1𝑣∈𝑻 𝑢,𝑣 ∈𝐸 (𝑺 = 𝑢 ∈ 𝑺 𝑓 𝑢 = 1 , 𝑻 = {𝑣 ∈ 𝑻|𝑓 𝑣 = −1}) 𝑢,𝑣 ∈𝐸 σ 𝑢,𝑣 ∈𝐸 1[𝑢 ∈ 𝑺]1[𝑣 ∈ 𝑻] は𝑺と𝑻の間の辺の本数、 𝑉𝑎𝑟 𝒇 の最小化問題は 𝑺 = 𝑢 ∈ 𝑺 𝑓 𝑢 ≥ 0 , 𝑻 = {𝑣 ∈ 𝑻|𝑓 𝑣 ≤ 0}と定義した最小カット問題と近似できる。 8

固有値からグラフを推定 複数の連結成分を持つグラフの固有値 命題：連結成分が𝑲個あるグラフのラプラシアン𝑳は重複度𝑲の固有値0を持つ。 グラフ𝐆が連結成分𝑮1 𝑮2 𝑮3 を持つとする。 𝑮1 𝒉1 = 1 0 0 0 , 𝒉2 = 0 0 0 0 0 0 0 1/ 3 , 𝒉1 = 0 0 1/ 3 1/ 3 0 1/2 1/2 0 1/2 1/2 0 0 𝒗𝟏 𝒗𝟐 𝑮3 𝒗𝟓 𝒗𝟒 𝒗𝟑 𝒗𝟔 𝑮2 𝒗𝟖 𝒗𝟕 𝒉1 , 𝒉2 , 𝒉3 は、互いに直行し、 連結成分内の辺の両端の値が等しいので、固有値は 𝑉𝑎𝑟 𝒉𝑖 = σ 𝑢,𝑣 ∈𝐸(𝑓 𝑢 − 𝑓(𝑣))2 ＝0 (𝑖 = 1,2,3) 1 1 1 1 1 𝒉= 2 2 1 1 1 1 この定数関数基底は𝒉 = 1 2 2 𝒉1 + 3 1 𝒉2 + 𝒉3 で表せるので、固有ベクト 2 2 2 ル𝒉, 𝒉1 , 𝒉2 , 𝒉3 で重複度が4とはならない。（固有ベクトルは一次独立） 9

固有値からグラフを推定 𝑲個の連結成分に近いグラフ（クラスタ）を持つとき、 固有値𝜆1 , 𝜆2 , … , 𝜆𝑘 は０に近くなる。 例えば、 𝜆1 = 0, 𝜆2 = 10, 𝜆3 = 35, 𝜆4 = 40, 𝜆5 = 110, …のような固有値を持つ グラフは、 𝜆2 が小さいので、強固な2大クラスタがあり、 さらに𝜆1 , 𝜆2 , 𝜆3 , 𝜆4 が 小さいので、４つのクラスタがある。 𝜆1 = 0, 𝜆2 = 330, 𝜆3 = 350, 𝜆4 = 360, 𝜆5 = 370, …のような固有値を持 つグラフは、 第２固有値以降が大きく、頂点間の結びつきが強く、グラフは非常 に密になる。 10

グラフフーリエ変換 グラフ上の信号𝒇をグラフフーリエ基底を用いて、 𝑛 𝒇=෍ 𝛼𝑖 𝒉𝑖 と表せる 𝑖=1 𝒇 → (𝛼1 , 𝛼2 , . . , 𝛼𝑛 )をグラフフーリエ変換と呼ぶ。 逆に、 (𝛼1 , 𝛼2 , . . , 𝛼𝑛 ) → 𝒇 = σ𝑛𝑖=1 𝛼𝑖 𝒉𝑖 を逆グラフフーリエ変換と呼ぶ。 アルゴリズム：グラフフーリエ変換 1. 𝑳 ← 𝐀 − 𝐃 2. 𝒉1 , 𝒉2 , … , 𝒉𝑛 ← 𝑳の正規直行固有ベク トル（固有値の小さい順） 3. 𝛼1 , 𝛼2 , . . , 𝛼𝑛 ← 𝒇𝑇 𝒉1 , 𝒇𝑇 𝒉2 , … , 𝒇𝑇 𝒉𝑛 4. 𝑟𝑒𝑡𝑢𝑟𝑛 𝛼1 , 𝛼2 , . . , 𝛼𝑛 𝑇 𝒇 𝒉𝑖 = ෍ 𝑛 𝑗=1 𝑇 𝛼𝑗 𝒉𝒋 𝒉𝑖 = 𝛼𝑖 アルゴリズム：逆グラフフーリエ変換 1. 𝑳 ← 𝐀 − 𝐃 2. 𝒉1 , 𝒉2 , … , 𝒉𝑛 ← 𝑳の正規直行固有ベク トル（固有値の小さい順） 3. 𝒇 ← σ𝑛𝑖=1 𝛼𝑖 𝒉𝑖 4. 𝑟𝑒𝑡𝑢𝑟𝑛 𝒇 0(𝑖 ≠ 𝑗) 𝒉𝒋 𝒉𝑖 = ቊ 1(𝑖 = 𝑗) 𝑇 11

グラフフーリエ変換 グラフフーリエ変換とフーリエ級数展開の関係 フーリエ級数展開は円環グラフのグラフフーリエ変換の頂点を離散化したものと 考えられる。グラフフーリエ基底は、 𝒉1 𝑣𝑖 = 1 𝒉2 (𝑣𝑖 ) = cos(2𝜋𝑖/𝑛) 𝒉3 (𝑣𝑖 ) = sin(2𝜋𝑖/𝑛) 𝒉4 (𝑣𝑖 ) = cos(4𝜋𝑖/𝑛) 𝒉5 (𝑣𝑖 ) = sin(4𝜋𝑖/𝑛) 𝑣1 𝑣2 𝒉1 𝒉2 𝒉3 𝒉4 12

13