GraphSAGE 2. 논문 기반 실제 계산

핵심 수식

GraphSAGE의 핵심은 다음 두 단계로 요약됩니다:

1. Aggregation (집계)

   $h_{\mathcal{N}(v)}^{(k)} = \text{AGGREGATE}_k\left(\{h_u^{(k-1)}, \forall u \in \mathcal{N}(v)\}\right)$

2. Update (업데이트)

   $h_v^{(k)} = \sigma\left(W^{(k)} \cdot \text{CONCAT}\left(h_v^{(k-1)}, h_{\mathcal{N}(v)}^{(k)}\right)\right)$

여기서

• $h_v^{(k)}$: 노드 $v$의 $k$번째 레이어에서의 임베딩
• $\mathcal{N}(v)$: 노드 $v$의 이웃 집합
• $W^{(k)}$: 학습 가능한 가중치 행렬
• $\sigma$: 활성화 함수 (이번 예제에서는 생략)

이제 이 수식을 실제 그래프와 숫자로 직접 계산해보겠습니다.

---

[0단계] 준비: 그래프와 초기 데이터

1. 예시 그래프 구조

노드와 간선은 다음과 같습니다:

• 노드: A, B, C, D, E, F
• 간선:
  • A–B, A–C, A–D
  • B–C
  • C–E, C–F

즉, 각 노드의 이웃은:

노드	이웃
A	B, C, D
B	A, C
C	A, B, E, F
D	A
E	C
F	C

목표: 노드 A의 2단계 임베딩 $h_A^{(2)}$를 계산하기

GraphSAGE는 바깥에서 안쪽으로 계산합니다:
2-hop 이웃 → 1-hop 이웃 → 타깃 노드

---

2. 초기 특징 벡터 ($k=0$)

모든 노드는 2차원의 초기 특징 벡터를 가집니다:

• $h_A^{(0)} = [1, 2]$
• $h_B^{(0)} = [3, 3]$
• $h_C^{(0)} = [4, 1]$
• $h_D^{(0)} = [2, 5]$
• $h_E^{(0)} = [1, 6]$
• $h_F^{(0)} = [4, 6]$

---

3. 설정

• Aggregator: Mean Aggregator (이웃 벡터의 평균)
• 가중치 행렬:
  $W^{(1)} = W^{(2)} = \begin{pmatrix} 1 & 0 & 0.5 & 0 \\ 0 & 1 & 0 & 0.5 \end{pmatrix}$
  → 입력은 4차원 (CONCAT 결과), 출력은 2차원
• 활성화 함수 $\sigma$: 계산 편의상 생략 (선형 변환만 수행)

---

[1단계] $k=1$: 1-hop 정보 집계

1-1. 노드 B의 $h_B^{(1)}$ 계산

• 이웃: A, C
• Aggregation:
  $h_{\mathcal{N}(B)}^{(1)} = \text{Mean}\left(h_A^{(0)}, h_C^{(0)}\right) = \text{Mean}([1,2], [4,1]) = [2.5, 1.5]$
• CONCAT:
  $\text{CONCAT}\left(h_B^{(0)}, h_{\mathcal{N}(B)}^{(1)}\right) = [3, 3, 2.5, 1.5]$
• Update:
  $h_B^{(1)} = \begin{pmatrix} 1 & 0 & 0.5 & 0 \\ 0 & 1 & 0 & 0.5 \end{pmatrix} \begin{pmatrix} 3 \\ 3 \\ 2.5 \\ 1.5 \end{pmatrix} = \begin{pmatrix} 3 + 1.25 \\ 3 + 0.75 \end{pmatrix} = [4.25,\ 3.75]$

---

1-2. 노드 C의 $h_C^{(1)}$ 계산

• 이웃: A, B, E, F
• Aggregation:
  $\text{Mean}([1,2], [3,3], [1,6], [4,6]) = \left[\frac{9}{4}, \frac{17}{4}\right] = [2.25,\ 4.25]$
• CONCAT: $[4, 1, 2.25, 4.25]$
• Update:
  $h_C^{(1)} = \begin{pmatrix} 1\cdot4 + 0.5\cdot2.25 \\ 1\cdot1 + 0.5\cdot4.25 \end{pmatrix} = [4 + 1.125,\ 1 + 2.125] = [5.125,\ 3.125]$

---

1-3. 노드 D의 $h_D^{(1)}$ 계산

• 이웃: A
• Aggregation: $h_{\mathcal{N}(D)}^{(1)} = h_A^{(0)} = [1, 2]$
• CONCAT: $[2, 5, 1, 2]$
• Update:
  $h_D^{(1)} = \begin{pmatrix} 1\cdot2 + 0.5\cdot1 \\ 1\cdot5 + 0.5\cdot2 \end{pmatrix} = [2.5,\ 6]$

---

1-4. (참고) 노드 A의 $h_A^{(1)}$ 계산

• 이웃: B, C, D
• Aggregation:
  $\text{Mean}([3,3], [4,1], [2,5]) = \left[\frac{9}{3}, \frac{9}{3}\right] = [3,\ 3]$
• CONCAT: $[1, 2, 3, 3]$
• Update:
  $h_A^{(1)} = \begin{pmatrix} 1\cdot1 + 0.5\cdot3 \\ 1\cdot2 + 0.5\cdot3 \end{pmatrix} = [2.5,\ 3.5]$

---

[2단계] $k=2$: 노드 A의 최종 임베딩 계산

이제 A가 이웃의 $h^{(1)}$ 정보를 받아 최종 임베딩을 만듭니다.

2-1. Aggregation (A의 이웃: B, C, D)

• $h_B^{(1)} = [4.25,\ 3.75]$

• $h_C^{(1)} = [5.125,\ 3.125]$

• $h_D^{(1)} = [2.5,\ 6]$

• 평균 계산:

  $h_{\mathcal{N}(A)}^{(2)} = \text{Mean}\left(h_B^{(1)}, h_C^{(1)}, h_D^{(1)}\right)$
  $= \left[ \frac{4.25 + 5.125 + 2.5}{3},\ \frac{3.75 + 3.125 + 6}{3} \right] = \left[ \frac{11.875}{3},\ \frac{12.875}{3} \right] \approx [3.9583,\ 4.2917]$

2-2. Update

• CONCAT:
  $\text{CONCAT}\left(h_A^{(1)}, h_{\mathcal{N}(A)}^{(2)}\right) = [2.5,\ 3.5,\ 3.9583,\ 4.2917]$
• 행렬 곱:
  $h_A^{(2)} = \begin{pmatrix} 1 & 0 & 0.5 & 0 \\ 0 & 1 & 0 & 0.5 \end{pmatrix} \begin{pmatrix} 2.5 \\ 3.5 \\ 3.9583 \\ 4.2917 \end{pmatrix} = \begin{pmatrix} 2.5 + 0.5 \times 3.9583 \\ 3.5 + 0.5 \times 4.2917 \end{pmatrix}$
  $= \begin{pmatrix} 2.5 + 1.97915 \\ 3.5 + 2.14585 \end{pmatrix} \approx [4.479,\ 5.646]$

최종 결과:

$h_A^{(2)} \approx [4.48,\ 5.65]$

---

결론: GraphSAGE가 만든 "지능적인" 임베딩

단계	노드 A의 임베딩
초기 ($k=0$)	$[1,\ 2]$
1단계 ($k=1$)	$[2.5,\ 3.5]$
2단계 ($k=2$)	$[4.48,\ 5.65]$

처음에는 A만의 정보였던 벡터가,
→ 1단계에서는 B, C, D의 직접 이웃 정보를 흡수하고,
→ 2단계에서는 E, F 같은 2-hop 이웃의 정보까지 간접적으로 포함하게 됩니다.

이 최종 벡터 $h_A^{(2)}$는 그래프 내 A의 구조적 역할과 문맥을 풍부하게 표현합니다.
이제 이 벡터를 활용해 노드 분류, 링크 예측, 클러스터링 등 다양한 작업을 수행할 수 있습니다.

---

핵심 포인트 정리

• GraphSAGE는 전체 그래프를 보지 않고도 새로운 노드에 대한 임베딩을 생성할 수 있음 (inductive)
• Aggregation + Update 구조로 이웃 정보를 계층적으로 통합
• 실제 구현에서는 $W^{(k)}$를 학습하지만, 이 예제에서는 이해를 위해 고정된 값 사용
• Mean Aggregator 외에도 Max, LSTM 기반 aggregator도 가능