GCN (Graph Convolution Network)

GNN (Graph Neural Network)

• 그래프 자료구조를 다루기 위해 설계된 신경망 구조

source : Tistory

• 기존 DNN(CNN, RNN 등)은 격자(Grid) 자료 구조를 전제로 하며, 보통 하나의 샘플(row, sequence)을 입력받아 그 샘플 자체에 대한 예측값을 출력한다

• 그러나, 이러한 DNN은 샘플 간의 관계성을 직접적으로 학습하거나 예측하는 데 한계가 있다

• GNN은 그래프를 입력으로 받아 노드 간 관계, 엣지 구조, 그래프 전체 패턴에 집중하여 학습하고, 예측을 수행한다

GNN을 위한 그래프 자료 구조

• 동형/이종 그래프의 Edge, Node를 관리하는 방식에 대해 알아보자
• PyG(PyTorch Geometric), DGL (Deep Graph Library)을 많이 사용한다 (예시는 PyG 기준)

동형(homogeneous) 그래프

• 모든 노드와 엣지가 동일한 타입을 가지는 경우
• $N_{type}(Node) = 1 \;\text{AND} \; N_{type}(Edge) = 1$

source : Tistory

• Node : 모든 노드가 같은 타입이므로 하나의 특징 행렬로 관리할 수 있다

  • Person 특징 행렬 : $X_{Person} \in \mathbb{R}^{{N} \times d}$

• Edge : 일반적으로 Edge List 형태를 사용한다 ($2 \times N(\text{Edges})$)

# PyG 스타일, (0→1, 1→2, 2→0) 연결
edge_index = [[0, 1, 2],   # source
              [1, 2, 0]]   # target

---

이종(heterogeneous) 그래프

• 노드 타입이나 엣지 타입 중 하나라도 두 개 이상 존재하는 경우
• $N_{type}(Node) \geq 2 \;\text{OR} \; N_{type}(Edge) \geq 2$

source : Tistory

• Node : 노드 타입별로 schema가 다를 수 있어 때문에 별도의 특징 행렬로 관리한다

  • Actor 특징 행렬 : $X_{Actor} \in \mathbb{R}^{{N_{Actor}} \times d_{actor}}$
  • Movie 특징 행렬 : $X_{Movie} \in \mathbb{R}^{{N_{Movie}} \times d_{Movie}}$
  • Director 특징 행렬 : $X_{Director} \in \mathbb{R}^{{N_{Director}} \times d_{Director}}$

• Edge : 엣지 타입별로 별도 관리한다 (src_type, relation, dst_type)

# Actor  --Acted-->  Movie
# 예: 배우 인덱스 [0,  2,   42] 가 영화 인덱스 [10, 10, 123]에 출연
data['Actor', 'Acted', 'Movie'].edge_index = torch.tensor(
    [[  0,   2,   42],
     [ 10,  10,  123]], dtype=torch.long
)

# Director  --Directed-->  Movie
# 예: 감독 인덱스 [5,  7] 이 영화 인덱스 [10, 123]을 연출
data['Director', 'Directed', 'Movie'].edge_index = torch.tensor(
    [[  5,   7],
     [ 10, 123]], dtype=torch.long

---

Edge Attribute (공통)

• 관계의 특성
  • 가중치,
  • Actor-Movie 관계에서 [등장 시간, 출연료] 등의 다차원 특성
    를 edge_attr로 표현 가능

# PyG 스타일 : (2 x num_edges)
edge_index = torch.tensor([
    [0, 1, 2, 2],   # source 노드
    [1, 2, 0, 2]    # target 노드
], dtype=torch.long)

# 엣지 속성(여기서는 weight)
edge_attr = torch.tensor([1.0, 2.5, 0.5, 3.0], dtype=torch.float)

source : chatGPT

+) 방향성/가중치/순환/다중간선과 같은 그래프의 이론적 속성도 자연스럽게 표현 가능

+) 다차원 edge_attr를 실제로 활용하려면 edge-feature-aware(예 : NNConv) 레이어를 써야 한다

GNN 학습

학습 목표

• GCN의 학습 대상은 노드 임베딩이다 : "각 노드 $v$가 표현 벡터 $h_v$를 가지도록 학습"

source : Tistory

• Task 수준에 따라 노드 임베딩을 활용하는 방식이 다르다 :

Task 수준	예시	노드 임베딩 활용 방식
Node-level	사용자 분류, 문서 주제 분류	최종 노드 임베딩 $h_v$에 Softmax 적용
Link-level	친구 추천, 단백질–약물 결합 여부	두 노드 임베딩의 내적/MLP 활용
Graph-level	그래프 단위 라벨 예측	모든 노드 임베딩을 pooling(sum/mean/...)하여 활용

메시지 패싱 (Message Passing)

• GNN 노드 표현을 학습하는 일반적인 패러다임

• CNN은 격자(grid) 구조 위에서 동작한다.
  픽셀(=GNN에서의 노드)의 위치가 유클리드 공간에 의해 정확히 정의되어 있기 때문에,
  공간적으로 인접한 픽셀들의 합성곱하면, 지역적 패턴을 반영한 임베딩을 생성할 수 있다

• 그래프는 비유클리드 구조라서, 좌표나 격자가 없다. 대신, 엣지(Edge)가 “연결 관계”를 정의한다 →
  따라서, 특정 노드 $v$의 임베딩은 이웃 노드들의 특성 + 엣지 정보(메시지)를 받아와 갱신하는 방식으로 학습한다

---

• 메시지 패싱의 일반적 정의

  $h_v^{(k+1)} = U^{(k)}(h_v^{(k)}, M^{(k)}(\{h_v^{(k)}, h_u^{(k)}, e_{uv}) | u \in \mathcal{N} (v)\}))$

  • 풀어 해석하면:
    노드 $v$의 $k+1$번째 임베딩($h_v^{(k+1)}$)은
    자신의 이전 임베딩($h_v^{(k)}$)과
    이웃 노드들의 임베딩($h_u^{(k)}$) 및 엣지 정보($e_{uv}$))로부터 생성된 메시지를
    집계·결합하여 갱신($U^{(k)}$)한 결과

GCN의 메시지 패싱

• GNN 기본 형태인 GCN(Graph Convolution Network)의 메시지 패싱에 대해 알아보자
• GCN은 동형 그래프를 전제로 설계되었으며, CNN의 합성곱을 그래프 구조에 확장한 형태이다

• GCN에서는 메시지 패싱이 스펙트럴 그래프 합성곱을 단순화한 형태로 정의된다

  $H^{(k+1)} = \sigma(\hat D^{-1/2}\hat A \hat D^{-1/2}H^{(k)}W^{(k)})$

  • $H^{(k+1)}$ : $k$번째 레이어의 노드 임베딩 행렬 ()
    • $H^{(0)} = X$ : 노드 특징 행렬
  • $\hat A$ : $A + I$ : 인접 행렬 + 단위 행렬
    • self-loop를 추가해 자기 자신의 정보도 집계
  • $\hat D$ : $\hat A$의 차수 행렬 (대각 행렬)
    • 정규화 $D^{-1/2}\hat A \hat D^{-1/2}$로 노드별 이웃 수 차이가 보장됨
  • $W^{(k)}$ : 학습 가능한 가중치 행렬 (선형 변환)
  • $\sigma$ : 비선형 활성화 함수 (ReLU 등)

---

GCN의 발전 형태

• “이웃 집계를 어떻게 다르게 하나?”
• “업데이트 방식을 어떻게 바꾸나?”
• “출력/태스크를 어떻게 다르게 정의하나?”

모델	GCN 대비 확장 포인트	핵심 아이디어 / 차별점
GCN	Baseline	인접 행렬 정규화 + 단순 평균 집계 (메시지 패싱의 표준 형태)
GraphSAGE	샘플링, 집계 확장	전체 이웃 대신 샘플링, 다양한 집계 함수(mean, max, LSTM 등) 활용
GAT	Weighting 방식 확장	Attention 기반으로 이웃별 중요도를 학습 (가중 평균)
GAE	목적 함수(Task) 확장	GCN을 인코더로 사용, 디코더로 링크 예측 수행 (그래프 오토인코더)
DGCNN	출력 구조 확장	GCN 기반으로 그래프 전체 표현 학습, 정렬(pooling) 후 분류 수행