12.22 그래프 신경망(GNN)의 기초

12.22 그래프 신경망(GNN)의 기초

1. 그래프 신경망의 개요

그래프 신경망(Graph Neural Network, GNN)은 그래프 구조의 데이터에서 학습할 수 있는 신경망의 한 종류이다. 일반적인 신경망(예: 합성곱 신경망)이 격자나 시퀀스 같은 정규 구조의 데이터에 특화된 반면, GNN은 노드와 엣지로 구성된 임의의 그래프에서 동작한다. GNN은 사회 네트워크 분석, 분자 화학, 추천 시스템, 컴퓨터 비전 등 다양한 분야에서 활용되며, 로봇공학에서도 다중 로봇 시스템, 운동 계획, SLAM, 매니퓰레이션 등에서 점차 중요해지고 있다. 본 절에서는 GNN의 기초 개념, 아키텍처, 그리고 로봇공학 응용을 다룬다.

2. GNN의 동기

2.1 그래프 데이터의 도전

전통적인 신경망은 정규 구조의 데이터(이미지의 격자, 시퀀스)에 적용되었다. 그래프 데이터는 다음과 같은 도전을 제공한다.

  • 불규칙성: 노드의 차수가 다양하다.
  • 순서 무관성: 노드의 순서에 의존하지 않아야 한다.
  • 동형성: 동형 그래프는 같은 출력을 산출해야 한다.

2.2 GNN의 해법

GNN은 이러한 도전을 다음의 방법으로 해결한다.

  • 메시지 전달: 노드들이 이웃과 정보를 교환한다.
  • 순서 무관 집계: 합, 평균, 최대 등의 순서 무관 함수 사용
  • 공유된 가중치: 모든 노드에 같은 가중치 적용

3. GNN의 핵심 개념

3.1 노드 특징

각 노드는 특징 벡터(feature vector)를 가진다.

\mathbf{h}_v \in \mathbb{R}^d

여기서 d는 특징의 차원이다.

3.2 엣지 특징

엣지도 특징을 가질 수 있다.

\mathbf{e}_{uv} \in \mathbb{R}^{d_e}

3.3 메시지 전달

GNN의 핵심은 노드 사이의 메시지 전달이다. 각 노드는 이웃의 정보를 받아 자신의 특징을 갱신한다.

4. 메시지 전달 신경망

4.1 일반적 형태

메시지 전달 신경망(Message Passing Neural Network, MPNN)의 일반적 형태는 다음과 같다.

4.1.1 메시지 단계

각 엣지에서 메시지를 계산한다.

\mathbf{m}_{uv}^{(t)} = M_t(\mathbf{h}_u^{(t)}, \mathbf{h}_v^{(t)}, \mathbf{e}_{uv})

여기서 M_t는 학습 가능한 함수이다.

4.1.2 집계 단계

각 노드는 모든 이웃의 메시지를 집계한다.

\mathbf{m}_v^{(t)} = \sum_{u \in N(v)}\mathbf{m}_{uv}^{(t)}

또는 평균, 최대 등 다른 집계 함수를 사용할 수 있다.

4.1.3 갱신 단계

각 노드의 특징이 갱신된다.

\mathbf{h}_v^{(t+1)} = U_t(\mathbf{h}_v^{(t)}, \mathbf{m}_v^{(t)})

여기서 U_t는 학습 가능한 갱신 함수이다.

4.2 반복

이 과정을 T번 반복한다. T가 클수록 더 멀리 있는 노드의 정보가 전파된다.

5. 일반적 GNN 아키텍처

5.1 GCN (Graph Convolutional Network)

GCN(Graph Convolutional Network)은 가장 단순하고 인기 있는 GNN이다. 키프(Kipf)와 웰링(Welling)이 2017년에 제안하였다.

5.1.1 갱신 식

\mathbf{H}^{(t+1)} = \sigma(\hat{\mathbf{A}}\mathbf{H}^{(t)}\mathbf{W}^{(t)})

여기서

  • \mathbf{H}^{(t)}: 모든 노드의 특징 행렬
  • \hat{\mathbf{A}} = \tilde{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-1/2}: 정규화된 인접 행렬
  • \tilde{\mathbf{A}} = \mathbf{A} + \mathbf{I}: 자기 루프가 추가된 인접 행렬
  • \mathbf{W}^{(t)}: 학습 가능한 가중치
  • \sigma: 활성화 함수 (예: ReLU)

5.1.2 특성

GCN은 단순하면서도 효과적이다. 노드 분류, 그래프 분류 등에 사용된다.

5.2 GraphSAGE

GraphSAGE는 큰 그래프에 적합한 GNN이다. 햄릴턴(Hamilton) 등이 2017년에 제안하였다.

5.2.1 샘플링

GraphSAGE는 모든 이웃을 사용하지 않고, 일부 이웃을 샘플링한다. 이는 큰 그래프에서 효율적이다.

5.2.2 집계 함수

다양한 집계 함수가 가능하다.

  • Mean: 평균
  • LSTM: 순서를 무작위화한 LSTM
  • Pool: 최대 풀링

5.3 GAT (Graph Attention Network)

GAT(Graph Attention Network)는 어텐션 메커니즘을 사용한다. 벨리코빅(Veličković) 등이 2018년에 제안하였다.

5.3.1 어텐션 가중치

각 이웃에 다른 가중치를 부여한다.

\alpha_{uv} = \frac{\exp(\text{LeakyReLU}(\mathbf{a}^T[\mathbf{W}\mathbf{h}_u || \mathbf{W}\mathbf{h}_v]))}{\sum_{k \in N(v)}\exp(\text{LeakyReLU}(\mathbf{a}^T[\mathbf{W}\mathbf{h}_k || \mathbf{W}\mathbf{h}_v]))}

여기서 ||는 연결 연산이다.

5.3.2 갱신

\mathbf{h}_v^{(t+1)} = \sigma\!\left(\sum_{u \in N(v)}\alpha_{uv}\mathbf{W}\mathbf{h}_u^{(t)}\right)

5.3.3 멀티헤드 어텐션

여러 어텐션 헤드를 사용하여 다양한 관점을 학습할 수 있다.

5.4 MPNN

MPNN(Message Passing Neural Network)은 메시지 전달의 일반화된 형태이다. 다양한 GNN을 통일된 틀에서 다룬다.

5.5 Graph Isomorphism Network (GIN)

GIN은 이론적으로 가장 강력한 GNN 중 하나이다. Weisfeiler-Lehman 그래프 이형 시험과 동등한 표현력을 가진다.

6. GNN의 작업

6.1 노드 분류

각 노드에 라벨을 예측한다.

\hat{y}_v = \text{softmax}(\mathbf{W}_o\mathbf{h}_v^{(T)} + \mathbf{b}_o)

응용: 소셜 네트워크에서 사용자 분류

6.2 엣지 예측

두 노드 사이에 엣지가 존재할지 예측한다. 링크 예측이라고도 한다.

응용: 소셜 네트워크의 친구 추천, 추천 시스템

6.3 그래프 분류

전체 그래프에 라벨을 예측한다.

\hat{y}_G = \text{softmax}(\mathbf{W}_o\text{POOL}(\{\mathbf{h}_v^{(T)} : v \in V\}) + \mathbf{b}_o)

여기서 POOL은 그래프 수준의 풀링 함수이다.

응용: 분자의 성질 예측

6.4 그래프 회귀

그래프에 연속 값을 예측한다.

응용: 분자의 에너지 예측

7. 그래프 풀링

7.1 동기

그래프 분류에서는 노드 수준의 정보를 그래프 수준으로 집계해야 한다. 이를 그래프 풀링(graph pooling)이라 한다.

7.2 단순 풀링

가장 단순한 풀링은 모든 노드의 평균이나 합이다.

\mathbf{h}_G = \text{MEAN}(\{\mathbf{h}_v : v \in V\})

7.3 학습 가능한 풀링

학습 가능한 풀링 방법도 있다.

  • DiffPool: 학습된 클러스터링
  • TopK Pool: 가장 중요한 노드만 선택
  • SAGPool: 어텐션 기반 풀링

8. GNN의 표현력

8.1 Weisfeiler-Lehman 시험

Weisfeiler-Lehman(WL) 시험은 그래프 이형 검사의 휴리스틱이다. 1차 WL 시험은 가장 일반적이다.

8.2 GNN의 한계

대부분의 GNN은 1차 WL 시험과 동등한 표현력을 가진다. 이는 일부 그래프를 구분하지 못함을 의미한다.

8.3 더 강력한 GNN

WL 시험보다 강력한 GNN이 연구되고 있다. 고차 GNN, 위치 인코딩 등의 방법이 있다.

9. GNN의 학습

9.1 손실 함수

작업에 따라 다양한 손실 함수가 사용된다.

  • 분류: 교차 엔트로피
  • 회귀: 평균 제곱 오차
  • 링크 예측: 이진 교차 엔트로피

9.2 최적화

표준 신경망 최적화 알고리즘(SGD, Adam 등)이 사용된다.

9.3 정규화

드롭아웃, 가중치 감쇠 등의 정규화 기법이 적용된다.

9.4 데이터 증강

그래프 데이터의 증강은 다음과 같은 방법이 있다.

  • 노드 또는 엣지의 무작위 제거
  • 노드 특징의 노이즈 추가
  • 부분 그래프 샘플링

10. GNN의 응용

10.1 소셜 네트워크

소셜 네트워크에서 사용자 분류, 친구 추천, 영향력 분석 등에 GNN이 사용된다.

10.2 분자 화학

분자를 그래프(원자 = 노드, 결합 = 엣지)로 표현하고, GNN으로 분자의 성질을 예측한다.

10.3 추천 시스템

사용자-아이템 그래프에서 GNN으로 추천을 학습한다.

10.4 컴퓨터 비전

이미지의 객체 사이의 관계를 그래프로 모델링하고 GNN으로 학습한다.

10.5 자연어 처리

문장의 구문 트리나 지식 그래프에 GNN이 적용된다.

11. 로봇공학에서의 응용

11.1 다중 로봇 시스템

다중 로봇의 통신 그래프에 GNN이 적용된다. 분산 정책을 학습할 수 있다.

11.2 매니퓰레이션

매니퓰레이터의 운동학적 트리에 GNN이 적용된다. 객체 사이의 관계를 학습한다.

11.3 운동 계획

운동 계획의 그래프 표현에 GNN이 적용된다. 효율적인 경로를 학습할 수 있다.

11.4 점 군 처리

점 군을 그래프로 표현하고 GNN으로 처리한다. PointNet++, DGCNN 등이 대표적이다.

11.5 장면 그래프

장면의 객체와 관계를 그래프로 표현하고 GNN으로 분석한다. 매니퓰레이션과 환경 이해에 활용된다.

12. 응용 예시: 다중 로봇 정책 학습

다중 로봇 시스템에서 각 로봇의 정책을 GNN으로 학습할 수 있다. 통신 그래프 위에서 메시지 전달을 통해 협력 행동을 학습한다.

13. 응용 예시: 분자 성질 예측

신약 개발에서 분자의 성질(독성, 활성 등)을 GNN으로 예측한다. 이는 로봇 화학 실험의 효율성을 향상시킨다.

14. 응용 예시: 매니퓰레이션 계획

매니퓰레이션 작업에서 객체 사이의 관계를 그래프로 표현한다. GNN이 가능한 매니퓰레이션 시퀀스를 학습한다.

15. 응용 예시: 점 군 분류

라이다나 깊이 카메라로 측정한 점 군을 그래프로 표현하고, GNN으로 객체 분류를 수행한다.

16. 응용 예시: SLAM의 그래프 학습

SLAM의 자세 그래프 구조를 활용하여 GNN이 위치 인식이나 회로 폐쇄 검출을 학습할 수 있다.

17. 응용 예시: 군집 형성

군집 로봇의 형성 제어 정책을 GNN으로 학습한다. 각 로봇이 이웃의 정보를 사용하여 자신의 행동을 결정한다.

18. GNN의 한계

18.1 깊이의 문제

GNN의 층이 깊어지면 노드 특징이 비슷해지는 over-smoothing 현상이 발생한다.

18.2 동질성 가정

대부분의 GNN은 이웃이 비슷한 특징을 가진다고 가정한다. 이질적 그래프에서는 성능이 저하될 수 있다.

18.3 계산 복잡도

큰 그래프에서 GNN의 학습과 추론은 계산 비용이 크다.

18.4 표현력의 한계

WL 시험과 동등한 표현력은 일부 그래프 구조를 구분하지 못한다.

19. GNN의 발전 방향

19.1 더 깊은 GNN

Over-smoothing을 해결하기 위한 잔차 연결, 정규화 기법 등이 연구되고 있다.

19.2 이질 그래프 GNN

이질적 그래프(다양한 종류의 노드와 엣지)를 위한 GNN이 발전하고 있다.

19.3 시간 그래프 GNN

시간에 따라 변하는 그래프를 위한 GNN이 연구되고 있다.

19.4 자기 지도 학습

라벨이 없는 그래프 데이터로부터 학습하는 방법이 발전하고 있다.

19.5 설명 가능성

GNN의 결정을 설명하는 방법이 연구되고 있다.

20. 라이브러리

20.1 PyTorch Geometric

PyTorch Geometric (PyG)은 PyTorch 기반 GNN 라이브러리이다. 다양한 GNN 모델과 데이터셋을 제공한다.

import torch
from torch_geometric.nn import GCNConv

class GCN(torch.nn.Module):
    def __init__(self, num_features, num_classes):
        super().__init__()
        self.conv1 = GCNConv(num_features, 16)
        self.conv2 = GCNConv(16, num_classes)
    
    def forward(self, x, edge_index):
        x = self.conv1(x, edge_index)
        x = torch.relu(x)
        x = self.conv2(x, edge_index)
        return x

20.2 DGL (Deep Graph Library)

DGL은 Amazon이 개발한 GNN 라이브러리이다. PyTorch, TensorFlow, MXNet을 지원한다.

import dgl
import torch

g = dgl.graph((src, dst))
g.ndata['feat'] = torch.randn(num_nodes, num_features)

20.3 Spektral

Spektral은 TensorFlow/Keras 기반 GNN 라이브러리이다.

20.4 Jraph

Jraph는 JAX 기반 GNN 라이브러리이다.

21. 학습의 가치

GNN을 깊이 이해하는 것은 다음과 같은 이점을 제공한다.

  • 그래프 데이터의 학습 방법을 익힌다.
  • 다양한 응용 분야의 가능성을 이해한다.
  • 현대 신경망의 한 중요한 영역을 학습한다.
  • 로봇공학의 새로운 접근법을 탐색할 수 있다.
  • 학술 연구에 기여할 수 있다.

22. 학습 권장사항

22.1 직접 구현

GCN과 같은 단순한 GNN을 직접 구현해 본다. PyTorch나 TensorFlow를 사용한다.

22.2 라이브러리 활용

PyTorch Geometric의 튜토리얼을 따라가며 사용법을 익힌다.

22.3 응용 학습

표준 데이터셋(Cora, Citeseer, MUTAG 등)에 GNN을 적용해 본다.

22.4 로봇공학 응용

로봇공학 문제를 그래프로 모델링하고 GNN으로 해결해 본다.

23. GNN의 미래

23.1 대규모 학습

매우 큰 그래프에서의 GNN 학습이 발전하고 있다.

23.2 멀티모달 학습

GNN과 다른 신경망(CNN, Transformer)의 결합이 활발히 연구되고 있다.

23.3 사전 학습 모델

NLP의 BERT처럼 GNN의 사전 학습 모델이 개발되고 있다.

23.4 추론 기능

GNN의 추론 능력을 향상시키는 연구가 진행되고 있다.

24. 본 절의 의의

본 절은 그래프 신경망(GNN)의 기초를 다루었다. GNN은 그래프 구조의 데이터를 학습할 수 있는 강력한 도구이며, 로봇공학에서도 점차 중요해지고 있다. GNN의 이해는 학습 기반 로봇공학의 새로운 가능성을 열어준다.

25. 참고 문헌

  • Kipf, T. N., & Welling, M. (2017). “Semi-supervised classification with graph convolutional networks.” International Conference on Learning Representations.
  • Hamilton, W., Ying, Z., & Leskovec, J. (2017). “Inductive representation learning on large graphs.” Advances in Neural Information Processing Systems, 30, 1024–1034.
  • Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., & Bengio, Y. (2018). “Graph attention networks.” International Conference on Learning Representations.
  • Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., & Dahl, G. E. (2017). “Neural message passing for quantum chemistry.” International Conference on Machine Learning, 1263–1272.
  • Xu, K., Hu, W., Leskovec, J., & Jegelka, S. (2019). “How powerful are graph neural networks?” International Conference on Learning Representations.
  • Hamilton, W. L. (2020). Graph Representation Learning. Morgan & Claypool.

version: 1.0