---
title: 【グラフニューラルネットワーク】7.1
tags: 
author: [京都大学人工知能研究会KaiRA](https://convert.docswell.com/user/kyoto-kaira)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/5EG345157L.jpg?width=480
description: 【グラフニューラルネットワーク】7.1 by 京都大学人工知能研究会KaiRA
published: July 08, 24
canonical: https://convert.docswell.com/s/kyoto-kaira/5VVQL4-2024-07-08-192845
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/5EG345157L.jpg)

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


# Page. 2

![Page Image](https://bcdn.docswell.com/page/4JQ5GZDL7P.jpg)

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


# Page. 3

![Page Image](https://bcdn.docswell.com/page/K74953Z5E1.jpg)

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


# Page. 4

![Page Image](https://bcdn.docswell.com/page/LJ1KW1R27G.jpg)

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


# Page. 5

![Page Image](https://bcdn.docswell.com/page/GJWD681272.jpg)

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


# Page. 6

![Page Image](https://bcdn.docswell.com/page/4EZGY8P4J3.jpg)

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


# Page. 7

![Page Image](https://bcdn.docswell.com/page/Y76YDPMGEV.jpg)

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 | &lt; 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


# Page. 8

![Page Image](https://bcdn.docswell.com/page/G75G3KZX74.jpg)

7.1 過平滑化現象とは
定理7.2の意味
def
r = max | 1 − λi | &lt; 1,
i=2,…,n
スペクトル領域でi = 2,…, n番目の信号の成分は、r ( &lt; 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


# Page. 9

![Page Image](https://bcdn.docswell.com/page/9J2YZWRQJR.jpg)

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


# Page. 10

![Page Image](https://bcdn.docswell.com/page/DEYGRLDYEM.jpg)

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


# Page. 11

![Page Image](https://bcdn.docswell.com/page/VJNGD46R78.jpg)

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


# Page. 12

![Page Image](https://bcdn.docswell.com/page/YE9WGQLZE3.jpg)

付録
12


# Page. 13

![Page Image](https://bcdn.docswell.com/page/GE8NVGWY7D.jpg)

7.1 過平滑化現象とは
定理7.1の証明(1/4)
Lsym = In − Â 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 &gt; 0である.
13


# Page. 14

![Page Image](https://bcdn.docswell.com/page/LELP5GN97R.jpg)

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


# Page. 15

![Page Image](https://bcdn.docswell.com/page/4JM43QXV7W.jpg)

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


# Page. 16

![Page Image](https://bcdn.docswell.com/page/PJRWQ8NW79.jpg)

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 Â Lsymhjsym
∑
j=2
n
1
L 12
L sym
= αi11 D 1n +
αij(1 − λj) hj
→ αi1D 2 1n
∑
L→∞
j=2
16


# Page. 17

![Page Image](https://bcdn.docswell.com/page/PEXP58NV7X.jpg)

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


# Page. 18

![Page Image](https://bcdn.docswell.com/page/3EKD6KN5JD.jpg)

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


# Page. 19

![Page Image](https://bcdn.docswell.com/page/L73R6ZV1J5.jpg)

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


# Page. 20

![Page Image](https://bcdn.docswell.com/page/87DYVR8K7G.jpg)

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


# Page. 21

![Page Image](https://bcdn.docswell.com/page/VJP6VW83E8.jpg)

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 &lt; 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


# Page. 22

![Page Image](https://bcdn.docswell.com/page/2EV3Z8NN7Q.jpg)

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


