GCN의 전파 규칙 이해하기2

HanJu Han·2025년 10월 11일

정규화된 GCN 전파 규칙 (Normalized GCN Propagation Rule)

핵심 목표

정규화된 GCN 전파 규칙은 다음과 같습니다:

H^{(i+1)} = \sigma\left( \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} H^{(i)} W^{(i)} \right)

이 수식이 왜 필요한지, 각 기호가 무엇을 의미하는지, 실제 숫자로 어떻게 계산되는지를 기초부터 아주 자세히 설명합니다.

1. 왜 정규화가 필요한가? — 기본 전파 규칙의 문제점

기본 GCN 전파 규칙:

H^{(i+1)} = \sigma(A H^{(i)} W^{(i)})

문제: 이웃 수에 따라 정보량이 치우침

노드 A: 이웃 100개 → $A H^{(i)}$ 결과가 과도하게 증폭됨
노드 B: 이웃 1개 → 결과가 작음

→ 학습 불안정 및 노드 간 표현 편향 발생

해결책: 이웃 정보를 정규화하여 공정하게 반영

2. 정규화를 위한 3가지 핵심 요소

$\tilde{A} = A + I$ — Self-loop 추가

$A$ : 원본 인접 행렬
$I$ : 단위 행렬
의미: 각 노드가 자기 자신의 정보도 포함하도록 연결합니다.

$\tilde{D}$ — 차수 행렬 (Degree Matrix)

$\tilde{D}$ 는 대각 행렬이며, $\tilde{D}_{ii} = \sum_{j} \tilde{A}_{ij}$
즉, 노드 $i$ 의 총 연결 수 (self-loop 포함)입니다.

$\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}$ — 정규화된 인접 행렬

목적: 이웃이 많은 노드의 영향력을 줄이고, 적은 노드의 영향력을 높여 균형 잡힌 정보 전달을 보장합니다.
직관: 노드 $i$ 와 $j$ 사이의 연결 강도 = $\frac{1}{\sqrt{d_i d_j}}$

이 방식은 대칭 정규화(symmetric normalization)라 불립니다.

3. 실제 예시로 단계별 계산 (새로운 데이터 적용)

그래프 정의

노드: 0, 1, 2, 3
엣지: (0, 1), (1, 2), (1, 3), (3, 0)

→ 원본 인접 행렬 $A$ :

A = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ \end{bmatrix}

Step 1: $\tilde{A} = A + I$ — Self-loop 추가

\tilde{A} = A + I = \begin{bmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ \end{bmatrix}

Step 2: 차수 행렬 $\tilde{D}$ 계산

각 행의 합: $d_0=2, d_1=3, d_2=2, d_3=3$ .

\tilde{D} = \begin{bmatrix} 2 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 3 \\ \end{bmatrix}

Step 3: $\tilde{D}^{-1/2}$ 계산

\tilde{D}^{-1/2} = \begin{bmatrix} \frac{1}{\sqrt{2}} & 0 & 0 & 0 \\ 0 & \frac{1}{\sqrt{3}} & 0 & 0 \\ 0 & 0 & \frac{1}{\sqrt{2}} & 0 \\ 0 & 0 & 0 & \frac{1}{\sqrt{3}} \\ \end{bmatrix} \approx \begin{bmatrix} 0.7071 & 0 & 0 & 0 \\ 0 & 0.5774 & 0 & 0 \\ 0 & 0 & 0.7071 & 0 \\ 0 & 0 & 0 & 0.5774 \\ \end{bmatrix}

Step 4: 정규화된 인접 행렬 $M = \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}$ 계산

(Step 1~3이 동일하므로, 결과 행렬 $M$ 은 이전과 동일합니다.)

M = \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} = \begin{bmatrix} 0.5000 & 0.4082 & 0 & 0 \\ 0 & 0.3333 & 0.4082 & 0.3333 \\ 0 & 0.4082 & 0.5000 & 0 \\ 0.4082 & 0 & 0.4082 & 0.3333 \\ \end{bmatrix}

✅ 이 행렬의 각 원소 $(i,j)$ 는 노드 $i$ 가 노드 $j$ 로부터 받는 정규화된 정보 비율을 나타냅니다.

Step 5: 전파 규칙 적용 (새로운 $H^{(0)}$ 및 $W^{(0)}$ 사용)

초기 임베딩 $H^{(0)} \in \mathbb{R}^{4 \times 2}$ (모든 값 양수)

H^{(0)} = \begin{bmatrix} 1.0 & 1.0 \\ 2.0 & 2.0 \\ 3.0 & 3.0 \\ 4.0 & 4.0 \\ \end{bmatrix}

가중치 $W^{(0)} \in \mathbb{R}^{2 \times 2}$ (모든 값 양수)

W^{(0)} = \begin{bmatrix} 0.1 & 0.2 \\ 0.3 & 0.4 \\ \end{bmatrix}

1) $M H^{(0)}$ 계산 (이웃 정보 집계)

M H^{(0)} = \begin{bmatrix} 0.5000 & 0.4082 & 0 & 0 \\ 0 & 0.3333 & 0.4082 & 0.3333 \\ 0 & 0.4082 & 0.5000 & 0 \\ 0.4082 & 0 & 0.4082 & 0.3333 \\ \end{bmatrix} \begin{bmatrix} 1.0 & 1.0 \\ 2.0 & 2.0 \\ 3.0 & 3.0 \\ 4.0 & 4.0 \\ \end{bmatrix} = \begin{bmatrix} 1.3164 & 1.3164 \\ 3.2244 & 3.2244 \\ 2.3164 & 2.3164 \\ 2.9660 & 2.9660 \\ \end{bmatrix}

2) $\times W^{(0)}$ 계산 (선형 변환)

\begin{bmatrix} 1.3164 & 1.3164 \\ 3.2244 & 3.2244 \\ 2.3164 & 2.3164 \\ 2.9660 & 2.9660 \\ \end{bmatrix} \begin{bmatrix} 0.1 & 0.2 \\ 0.3 & 0.4 \\ \end{bmatrix} = \begin{bmatrix} 0.5266 & 0.7898 \\ 1.2898 & 1.9346 \\ 0.9266 & 1.3898 \\ 1.1864 & 1.7796 \\ \end{bmatrix}

3) ReLU 적용 ( $\sigma = \text{ReLU}$ )

모든 값이 양수이므로, ReLU를 적용해도 값이 유지됩니다.

H^{(1)} = \text{ReLU}\left( \begin{bmatrix} 0.5266 & 0.7898 \\ 1.2898 & 1.9346 \\ 0.9266 & 1.3898 \\ 1.1864 & 1.7796 \\ \end{bmatrix} \right) = \begin{bmatrix} 0.5266 & 0.7898 \\ 1.2898 & 1.9346 \\ 0.9266 & 1.3898 \\ 1.1864 & 1.7796 \\ \end{bmatrix}

결과 해석: $H^{(1)}$ 은 노드 0, 1, 2, 3의 새로운 임베딩을 나타냅니다. 이 임베딩은 이웃 노드의 정보를 정규화된 방식으로 통합하여 생성되었으며, 다음 레이어의 입력으로 사용됩니다.

정규화의 효과 요약

노드	이웃 수 (self-loop 포함)	기본 전파 $A H$ (합산)	정규화 전파 $M H$ (평균화)
0	2	$1.0+2.0=3.0$ (큼)	$1.3164$ (정규화됨)
1	3	$2.0+3.0+4.0=9.0$ (매우 큼)	$3.2244$ (정규화됨)
2	2	$2.0+3.0=5.0$ (큼)	$2.3164$ (정규화됨)
3	3	$1.0+3.0+4.0=8.0$ (매우 큼)	$2.9660$ (정규화됨)

결과: 정규화된 전파 $M H$ 를 사용하면, 이웃이 2개인 노드 0과 이웃이 3개인 노드 1, 3이 받는 정보의 크기가 훨씬 더 균형 잡히게 조정됩니다. 이는 안정적이고 공정한 학습을 가능하게 합니다.

결론

정규화된 GCN 전파 규칙은 다음과 같이 요약됩니다:

H^{(i+1)} = \sigma\left( \underbrace{\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}}_{\text{정규화된 구조}} \underbrace{H^{(i)}}_{\text{현재 임베딩}} \underbrace{W^{(i)}}_{\text{학습 가중치}} \right)

이 수식은 GCN이 그래프 구조를 활용하여 노드 임베딩을 효과적으로 업데이트하는 핵심 메커니즘입니다.

HanJu Han

시리즈를 기반으로 작성하였습니다.

이전 포스트

GCN의 전파 규칙 이해하기1

다음 포스트

GCN의 전파 규칙 이해하기2

정규화된 GCN 전파 규칙 (Normalized GCN Propagation Rule)

핵심 목표

1. 왜 정규화가 필요한가? — 기본 전파 규칙의 문제점

문제: 이웃 수에 따라 정보량이 치우침

2. 정규화를 위한 3가지 핵심 요소

$\tilde{A} = A + I$ — Self-loop 추가

$\tilde{D}$ — 차수 행렬 (Degree Matrix)

$\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}$ — 정규화된 인접 행렬

3. 실제 예시로 단계별 계산 (새로운 데이터 적용)

그래프 정의

Step 1: $\tilde{A} = A + I$ — Self-loop 추가

Step 2: 차수 행렬 $\tilde{D}$ 계산

Step 3: $\tilde{D}^{-1/2}$ 계산

Step 4: 정규화된 인접 행렬 $M = \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}$ 계산

Step 5: 전파 규칙 적용 (새로운 $H^{(0)}$ 및 $W^{(0)}$ 사용)

초기 임베딩 $H^{(0)} \in \mathbb{R}^{4 \times 2}$ (모든 값 양수)

가중치 $W^{(0)} \in \mathbb{R}^{2 \times 2}$ (모든 값 양수)

1) $M H^{(0)}$ 계산 (이웃 정보 집계)

2) $\times W^{(0)}$ 계산 (선형 변환)

3) ReLU 적용 ( $\sigma = \text{ReLU}$ )

정규화의 효과 요약

결론

GCN의 전파 규칙 이해하기1

GCN 정규화 행렬, (1,3) 성분을 Step-by-Step으로 계산

0개의 댓글

GCN의 전파 규칙 이해하기2

정규화된 GCN 전파 규칙 (Normalized GCN Propagation Rule)

핵심 목표

1. 왜 정규화가 필요한가? — 기본 전파 규칙의 문제점

문제: 이웃 수에 따라 정보량이 치우침

2. 정규화를 위한 3가지 핵심 요소

A~=A+I\tilde{A} = A + IA~=A+I — Self-loop 추가

D~\tilde{D}D~ — 차수 행렬 (Degree Matrix)

D~−1/2A~D~−1/2\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}D~−1/2A~D~−1/2 — 정규화된 인접 행렬

3. 실제 예시로 단계별 계산 (새로운 데이터 적용)

그래프 정의

Step 1: A~=A+I\tilde{A} = A + IA~=A+I — Self-loop 추가

Step 2: 차수 행렬 D~\tilde{D}D~ 계산

Step 3: D~−1/2\tilde{D}^{-1/2}D~−1/2 계산

Step 4: 정규화된 인접 행렬 M=D~−1/2A~D~−1/2M = \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}M=D~−1/2A~D~−1/2 계산

Step 5: 전파 규칙 적용 (새로운 H(0)H^{(0)}H(0) 및 W(0)W^{(0)}W(0) 사용)

초기 임베딩 H(0)∈R4×2H^{(0)} \in \mathbb{R}^{4 \times 2}H(0)∈R4×2 (모든 값 양수)

가중치 W(0)∈R2×2W^{(0)} \in \mathbb{R}^{2 \times 2}W(0)∈R2×2 (모든 값 양수)

1) MH(0)M H^{(0)}MH(0) 계산 (이웃 정보 집계)

2) ×W(0)\times W^{(0)}×W(0) 계산 (선형 변환)

3) ReLU 적용 (σ=ReLU\sigma = \text{ReLU}σ=ReLU)

정규화의 효과 요약

결론

GCN의 전파 규칙 이해하기1

GCN 정규화 행렬, (1,3) 성분을 Step-by-Step으로 계산

0개의 댓글

$\tilde{A} = A + I$ — Self-loop 추가

$\tilde{D}$ — 차수 행렬 (Degree Matrix)

$\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}$ — 정규화된 인접 행렬

Step 1: $\tilde{A} = A + I$ — Self-loop 추가

Step 2: 차수 행렬 $\tilde{D}$ 계산

Step 3: $\tilde{D}^{-1/2}$ 계산

Step 4: 정규화된 인접 행렬 $M = \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}$ 계산

Step 5: 전파 규칙 적용 (새로운 $H^{(0)}$ 및 $W^{(0)}$ 사용)

초기 임베딩 $H^{(0)} \in \mathbb{R}^{4 \times 2}$ (모든 값 양수)

가중치 $W^{(0)} \in \mathbb{R}^{2 \times 2}$ (모든 값 양수)

1) $M H^{(0)}$ 계산 (이웃 정보 집계)

2) $\times W^{(0)}$ 계산 (선형 변환)

3) ReLU 적용 ( $\sigma = \text{ReLU}$ )