Graph Neural Network (GNN)

그래프 신경망(GNN)은 그래프에서 직접 작동하는 신경망입니다. 그래프는 에지로 연결된 노드 집합이며 노드와 에지 모두 특징을 가질 수 있습니다. 분자(원자와 결합), 소셜 네트워크(사용자와 팔로우 관계), 도로망(교차로와 도로 구간), 3D 메시, 인간 골격의 관절은 모두 그래프입니다. 그래프에는 고정된 격자나 순서가 없고 노드마다 이웃의 수가 다르므로, 합성곱 신경망(CNN)의 슬라이딩 필터나 순환 신경망(RNN)의 단계별 입력 처리를 그대로 적용할 수 없습니다. GNN은 메시지 전달 방식으로 이 문제를 처리합니다. 각 노드는 이웃의 특징을 바탕으로 자신의 특징 벡터를 반복적으로 업데이트하여, 노드 자체의 속성과 그래프 내 위치를 모두 인코딩하는 노드 임베딩을 생성합니다.

메시지 전달 작동 방식#

GNN 레이어는 세 단계로 모든 노드를 업데이트합니다. 각 이웃은 보통 특징을 학습된 변환한 메시지를 보냅니다. 노드는 합계, 평균, 최댓값처럼 순서를 무시하는 함수로 들어오는 메시지를 집계합니다. 그런 다음 집계 결과와 자체 특징을 결합해 새로운 표현을 만듭니다. 집계 과정에서 순서를 무시하므로 결과는 노드에 어떤 번호를 부여했는지에 좌우되지 않습니다. Justin Gilmer와 동료들은 2017년에 많은 GNN을 이 메시지 전달 신경망 프레임워크의 사례로 설명했습니다. 마지막 레이어 이후에는 작업별 헤드가 노드 임베딩을 읽어 노드에 레이블을 지정하고, 누락된 엣지를 예측하거나, 전체 그래프를 분류합니다:

각 레이어는 노드의 관점을 홉 하나만큼 확장하므로, k개 레이어를 거친 노드 임베딩은 그래프에서 k개 엣지 이내에 있는 모든 노드, 즉 노드의 수용 영역에 있는 모든 노드에 영향을 받습니다. 아래의 PyTorch 코드는 노드 6개로 이루어진 경로 그래프를 만들고, Thomas Kipf와 Max Welling의 GCN에서 사용한 정규화를 적용한 그래프 합성곱 레이어 세 개를 적용한 다음, autograd를 사용해 각 레이어 이후 노드 0에 영향을 미치는 입력 노드를 나열합니다:

import torch
from torch import nn

# A path graph 0-1-2-3-4-5 as an adjacency matrix with self-loops
A = torch.eye(6)
for i in range(5):
    A[i, i + 1] = A[i + 1, i] = 1
deg = A.sum(dim=1)
A_hat = A / torch.sqrt(deg[:, None] * deg[None, :])  # GCN normalization D^-1/2 (A + I) D^-1/2

torch.manual_seed(0)
x = torch.randn(6, 4, requires_grad=True)  # 4 input features per node
layers = [nn.Linear(4, 4) for _ in range(3)]

h = x
for k, layer in enumerate(layers, start=1):
    h = torch.tanh(A_hat @ layer(h))  # each node mixes in its neighbors' transformed features
    grad = torch.autograd.grad(h[0].sum(), x, retain_graph=True)[0]
    print(f"After layer {k}, node 0 depends on nodes {grad.abs().sum(dim=1).nonzero().flatten().tolist()}")

[0, 1], [0, 1, 2], [0, 1, 2, 3]를 출력합니다. 노드 0의 수용 영역은 레이어마다 정확히 한 홉씩 커집니다.

일반적인 GNN 아키텍처#

• GCN: 그래프 합성곱 네트워크는 H′ = σ(D̃^(−1/2) Ã D̃^(−1/2) H W)를 계산합니다. 여기서 Ã는 셀프 루프가 포함된 인접 행렬이고 D̃는 그 차수 행렬입니다. 이는 각 노드와 이웃의 차수 가중 평균을 구한 뒤, 모든 노드가 공유하는 가중치 행렬 W를 적용합니다.
• GraphSAGE: 노드별로 고정된 수의 이웃을 샘플링하고 집계기를 학습하므로, 매우 큰 그래프로 확장할 수 있으며 학습 이후에 나타나는 노드도 임베딩할 수 있습니다.
• GAT: 그래프 어텐션 네트워크는 고정된 차수 기반 가중치 대신 학습된 어텐션 점수로 각 이웃의 가중치를 부여합니다.
• GIN: 그래프 동형 네트워크는 이웃을 합산하고 MLP를 적용합니다. Keyulu Xu와 동료들은 이 방식이 표준 메시지 전달의 이론적 한계인 Weisfeiler-Lehman 테스트만큼 그래프를 잘 구별할 수 있음을 증명했습니다.
• 그래프 트랜스포머: 모든 노드에 셀프 어텐션을 적용하고 그래프 구조에서 파생된 위치 인코딩을 추가합니다. 표준 트랜스포머 자체도 토큰으로 이루어진 완전 연결 그래프의 GNN입니다.

레이어를 많이 쌓으면 과도한 스무딩이 발생합니다. 반복적인 평균화로 노드 임베딩이 서로 가까워져 결국 구별할 수 없게 되므로, 원래 GCN이 두 개의 레이어를 사용한 것처럼 많은 GNN은 레이어를 두세 개만 사용합니다. PyTorch Geometric과 Deep Graph Library (DGL)는 희소 엣지 리스트에서 이러한 레이어를 효율적으로 구현합니다.

실제 적용 사례#

• 날씨 예측: Google DeepMind의 GraphCast는 2023년 Science에 발표되었으며, 지구 전체를 덮는 다중 스케일 메시에서 메시지 전달을 실행해 0.25° 해상도의 10일 예보를 1분 이내에 생성합니다. 또한 1,380개 검증 대상 중 90%에서 가장 정확한 운영용 결정론적 시스템보다 우수한 성능을 보였습니다.
• 신약 개발: 2020년 MIT 연구진은 분자 그래프를 바탕으로 항균 활성을 예측하도록 방향성 메시지 전달 네트워크를 학습시켰으며, 이를 이용해 알려진 항생제와 구조적으로 다른 화합물인 할리신을 찾아냈습니다. 할리신은 실험실 테스트에서 약물 내성 박테리아 다수를 사멸시켰습니다.
• 추천 시스템: Pinterest의 PinSage는 핀 30억 개와 보드, 엣지 180억 개로 이루어진 그래프에서 핀 임베딩을 학습했으며, 75억 개의 예제로 학습했습니다.
• 스켈레톤 기반 행동 인식: ST-GCN은 신체 관절을 노드로 취급하고, 각 프레임 안에서는 뼈대로 관절을 연결하며 인접 프레임에서는 동일한 관절끼리 연결한 다음, 그 결과로 만들어진 시공간 그래프에서 행동을 분류합니다. YOLO26 포즈 추정 모델은 매 프레임마다 사람별 COCO 키포인트 17개를 반환하며, 이러한 스켈레톤 그래프는 해당 관절 좌표로 구성됩니다.

GNN과 관련 개념 비교#

• 지식 그래프: 사실을 개체-관계-개체의 트리플로 저장하는 데이터 구조입니다. GNN은 지식 그래프에서 학습할 수 있는 모델이며, 예를 들어 누락된 링크를 예측하는 데 사용할 수 있습니다.
• 기하학적 딥러닝: 데이터의 대칭성을 중심으로 구축된 네트워크를 다루는 더 넓은 분야입니다. 격자에서 작동하는 CNN, 그래프에서 작동하는 GNN, 메시와 다양체에서 작동하는 모델을 포함합니다.
• CNN: 이미지에 적용된 CNN은 격자 그래프에서 메시지 전달을 수행하는 특수한 사례입니다. 격자에서는 모든 픽셀이 고정된 상대적 위치에 동일한 수의 이웃을 가지므로 CNN은 각 이웃 위치마다 별도의 가중치를 학습할 수 있습니다. 불규칙한 그래프의 GNN은 이 방식을 사용할 수 없습니다.