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

グラフニューラルネットワーク 7.1 過平滑化現象とは 京都大学大学院情報学研究科 M2 若井雄紀 1

7.1 過平滑化現象とは 過平滑化現象 • 過平滑化現象(over-smoothing)とは、 GNNの出力がすべての頂点で同じ、またはほとんど同じ値になる現象。 • 各頂点の入力特徴量 X はほとんど無視され、グラフ構造のみに依存する。 • GNNは周囲の頂点の情報を取り込む操作を繰り返すが、 この操作が多いとすべての頂点で情報が一様になってしまうことが原因。 • スペクトルグラフ理論の文脈では、 GNNは低周波信号を強調するため、層が深いと低周波信号しか残らない。 究極的には最も低周波な信号である定数成分しか残らない。 2

7.1 過平滑化現象とは 過平滑化現象の例 埋め込みはRGBの3次元ベクトルであり、層を経るごとに 埋め込みベクトルが一様に近づいている。 3

7.1 過平滑化現象とは 記法 自己ループを追加した隣接行列をÃ ∈ ℝn×nとする。 隣接行列を2通りの方法で正規化する。 推移ラプラシアンで用いる正規化 Â rw = D̃−1 Ã − 12 − 12 ̂ 対称正規化ラプラシアンで用いる正規化 Asym = D̃ Ã D̃ この隣接行列を用いてGNNを表すと、 線形GNNの場合、 Z sym(L) = Â Lsym XW 推移ラプラシアンで用いる正規化 Z rw(L) = Â L XW 対称正規化ラプラシアンで用いる正規化 rw 4

7.1 過平滑化現象とは 線形GNNの過平滑化現象 線形GNNは、層が深すぎると定数信号の成分しか残らない。 定理7.1(線形GNNの過平滑化現象) 任意の連結グラフG = (V, E, X), 任意のパラメータW ∈ ℝd×dout、 各i = 1…doutについてαi, βi ∈ ℝ が存在して,、 1 sym(L) lim Z:,i = αi D 2 1n ∈ ℝn, lim Z:,irw(L) = βi1n ∈ ℝn L→∞ L→∞ となる。収束の速度は指数関数的である。 5

7.1 過平滑化現象とは 証明のスケッチ 1. 対称正規化ラプラシアンLsym = I − Â symの固有値λは、 最も低周波な信号である、定数信号に対応する固有値はλ1 = 0、 他の信号に対応する固有値λi (i = 2,…, n)は0 < λi < 2を満たす。 2. 正規化された隣接行列Â symの固有値λ′は、 定数信号に対応する固有値はλ′1 = 1、 他の信号に対応する固有値λ′i (i = 2,…, n)は−1 < λ′i < 1を満たす。 （ちなみに固有ベクトルの組は同じ） 3. i番目の信号に対応する固有ベクトルをhiとすると、Â Lsym hi = (λ′i )L hi      層が深くなりLが大きくなるほど、定数信号以外の成分は0に収束する。 6

7.1 過平滑化現象とは ReLU非線形関数を用いたGNNの過平滑化現象 ReLU非線形GNNも、層が深すぎると定数信号の成分しか残らない。 定理7.2(ReLU非線形GNNの過平滑化現象) 任意の連結グラフG = (V, E, X)と任意のパラメータW (1), …, W (L)について 対称正規化ラプラシアンL symの固有値をλ1 ≤ λ2 ≤ … ≤ λnとする。 def def r = max | 1 − λi | < 1, 作用素ノルム sl = ∥W (l)∥op= max W (l) xとして i=2,…,n lim r L L→∞ x:∥x∥2=1 L s = 0が成り立つならば、各i = 1,…, doutについてあるα1, …αdoutが存在して ∏ l l=1 1 (L) lim ∥Z:,i − αL D 2 1n∥ = 0かつ lim Var sym(Z:,i(L)) = 0 L→∞ L→∞ 特に、Z (L) 1 (L) が収束するならば、各i = 1,…, doutについてα ∈ ℝが存在してZ:,i → αD 2 1n 7

7.1 過平滑化現象とは 定理7.2の意味 def r = max | 1 − λi | < 1, i=2,…,n スペクトル領域でi = 2,…, n番目の信号の成分は、r ( < 1) 倍以下に減衰する。 def 作用素ノルム sl = ∥W (l)∥op= max W (l) xとして x:∥x∥2=1 作用素ノルムslは線形写像Wによって入力が最大何倍増幅するかを表す。 lim r L L→∞ lim r L L→∞ L s = 0が成り立つならば、以降… ∏ l l=1 L s = 0のとき、増幅よりも減衰による影響が強く、信号が減衰する。 ∏ l l=1 8

7.1 過平滑化現象とは 定理7.2の意味 各i = 1,…, doutについてあるα1, …αdoutが存在して 1 (L) lim ∥Z:,i − αL D 2 1n∥ = 0かつ lim Var sym(Z:,i(L)) = 0 L→∞ L→∞ 1 2 各頂点における信号を表すn次元ベクトルは、i番目の信号はD 1nのαi倍に漸近する。 特に、Z (L) 1 (L) が収束するならば、各i = 1,…, doutについてα ∈ ℝが存在してZ:,i → αD 2 1n 1 2 各頂点における信号を表すn次元ベクトルは、すべての信号がD 1nのα倍に漸近する。 9

7.1 過平滑化現象とは 証明のスケッチ 定数信号以外(h2, …, hn)の成分の大きさをν(X)で表すと 1. ν(Â sym X) ≤ rν(X) (l) ) ≤∥W (l)∥opν(X) = slν(X) 3. ν(ReLU(X)) ≤ ν(X) が成り立つ。よって、ν(ReLU(Â sym XW (l))) ≤ rslν(X) 2. ν(XW したがって、 lim r L L→∞ L ∏ l=1 sl = 0が成り立つならば、 定数信号以外の成分の大きさは0に収束する。 10

7.1 過平滑化現象とは まとめ • 過平滑化現象(over-smoothing)とは、 GNNの出力がすべての頂点で同じ、またはほとんど同じ値になる現象。 • GNNは周囲の頂点の情報を取り込む操作を繰り返すが、 この操作が多いとすべての頂点で情報が一様になってしまうことが原因。 • スペクトルグラフ理論の文脈では、 GNNは低周波信号を強調するため、層が深いと低周波信号しか残らない。 究極的には最も低周波な信号である定数成分しか残らない。 • 線形GNN、ReLU非線形GNNの場合、過平滑化現象が起こることを証明した。 11

付録 12

7.1 過平滑化現象とは 定理7.1の証明(1/4) Lsym = In − Â sym の固有値をλ1 ≤ λ2 ≤ … ≤ λnとする Var sym T (f) = f L sym f= ∑ {u,v}∈ℰ 1 2 D 1n = ( deg(v1), …, ( f(u) deg(u) − f(v) deg(v) T deg(vn)) であるからVar sym )2より 1 2 (D 1n) = 0 1 2 よって, D 1はλ = 0に属する固有ベクトル 1 2 また、hがD 1の定数倍でないとき, λ2 > 0である. 13

7.1 過平滑化現象とは 定理7.1の証明(2/4) hv 2 ∑ deg(u) deg(v) {u,v}∈ℰ {u,v}∈ℰ ∵ (a − b)2 ≤ (a − b)2 + (a + b)2 = 2(a 2 + b 2) hv2 hu2 = 2{ + } ∑ deg(u) deg(v) {u,v}∈ℰ λ= ∑ hu ( − ) ≤ 2{ ( hu deg(u) 2 ) +( hv deg(v) )2} hu2 =2 deg(u) ∑ deg(u) u =2 ∑ u hu2 = 2∥h∥2 =2 14

7.1 過平滑化現象とは 定理7.1の証明(3/4) Â symの固有ベクトルを考える Lsymの固有値λに属する固有ベクトルhについて Lsym = In − Â symより(In − Â sym)h = λhであるから Â sym h = (1 − λ)h hはÂ symの固有値1 − λに属する固有ベクトルとなっている Â symの固有ベクトルはn個, h1, …, hnの一次独立性から 過不足なくÂ symの固有ベクトルとなる したがって1 = 1 − λ1 > 1 − λ2 ≥ , …,1 − λn > − 1 15

7.1 過平滑化現象とは 定理7.1の証明(4/4) sym sym 固有ベクトルによる直交基底h , …, hn を用いて表すと、 1 n 1 sym 2 (XW):,i = αi1D 1n + αij hj とすると ∑ j=2 n 1 sym(L) L L ̂ ̂ Z:,i = Asym(XW):,i = αi1Asym D 2 1n + αij  Lsymhjsym ∑ j=2 n 1 L 12 L sym = αi11 D 1n + αij(1 − λj) hj → αi1D 2 1n ∑ L→∞ j=2 16

7.1 過平滑化現象とは 定理7.2の証明(1/6) Lsymの固有値をλ1, …, λnとして、 対応する正規直交固有ベクトルをh1, …, hnとする。 Xのi次元目の信号についてのj番目の低周波成分α(X)ijを導入。 すべての頂点についてi次元目の信号を集め、グラフフーリエ変換したときの基底hjの成分 つまり、X:,i = n ∑ j=1 α(X)ij hj 17

7.1 過平滑化現象とは 定理7.2の証明(2/6) def フロベニウスノルム∥X∥F = ∑ ij Xij2 = ∑ ij α(X)2ij h1以外の成分の大きさをν(X)と定義 つまりν(X) = d n i j=2 ∑∑ α(X)2ij 18

7.1 過平滑化現象とは 定理7.2の証明(3/6) Â sym X:,i = n ∑ j=1 Â symα(X)ij hj = n ∑ j=1 (1 − λj)α(X)ij hj j = 2,…, nについて | 1 − λj | < rであるから、 ν(Â sym X) ≤ rν(X) 19

7.1 過平滑化現象とは 定理7.2の証明(4/6) XW = n ∑ j=1 hj α(X)T:,jWより、 作用素ノルムの定義から∥α(X)T:,jW∥2 ≤ ∥α(X):,j∥2∥W∥op よって、ν(XW) ≤ ∥W∥opν(X) 20

7.1 過平滑化現象とは 定理7.2の証明(5/6) X+,ij = ReLU(Xij) = {0 Xij if ≥ 0 X−,ij = otherwise X = X+ − X−であり∥X∥F = ∥X+∥2F + ∥X−∥2F {0 −Xij if < 0 otherwise とすると ∥ReLU(X)∥2F = ∥X+∥2F よりReLUによるノルムの減少は∥X−∥2F h1についての減少は、∥X T h1∥22 − ∥X+T h1∥22 = ∥(X+ − X−)T h1∥22 − ∥X+T h1∥22 = − 2(X+T + h1)(X−T h1) + ∥X−T h1∥22 ≤ ∥X−T h1∥22 ≤ ∥X−∥2F よって、ν(X)2 − ν(X+)2 = (∥X∥2F − ∥X+∥2F ) − (∥X T h1∥22 − ∥X+T h1∥22) ≥ 0 したがって、ν(ReLU(X)) ≤ ν(X) 21

7.1 過平滑化現象とは 定理7.2の証明(6/6) 定数信号以外の成分の大きさをν(X)で表すと 1. ν(Â sym X) ≤ rν(X) (l) ) ≤∥W (l)∥opν(X) 3. ν(ReLU(X)) ≤ ν(X) が成り立つ。つまり、ν(ReLU(Â sym XW)) ≤ rslν(X) 2. ν(XW したがって、 lim r L L→∞ L ∏ l=1 sl = 0が成り立つならば、 定数信号以外の成分の大きさは0に収束する 22