ch13 - Graph Neural Networks
- GNN 핵심 아이디어: "내 이웃을 보면 나를 알 수 있다"
- Graph Representation
- GNN 주요 task 3가지
- Inductive vs. Transductive: GNN만의 독특한 학습 환경
- GNN을 더 강력하게 만드는 Advanced Topics
- 정리
CNN이 격자 데이터(이미지)를, 트랜스포머가 시퀀스 데이터(텍스트)를 다룬다면, GNN은 소셜 네트워크나 분자 구조처럼 불규칙한 관계형 데이터를 처리하기 위한 모델이다.
GNN 핵심 아이디어: "내 이웃을 보면 나를 알 수 있다"
GNN의 모든 것은 message passing 또는 neighborhood aggregation(이웃 정보 취합)이라는 한 가지 아이디어로 요약된다.
어떤 노드(사용자, 원자 등)의 정보를 업데이트하고 싶을 때, 다음과 같은 간단한 2단계를 거친다.
- 정보 수집(aggregate): 노드에 연결된 모든 이웃 노드들의 정보(임베딩)를 긁어모은다. 가장 단순한 방법은 이웃들 정보 벡터를 그냥 다 더하는 것.
- 정보 갱신(Update): 1에서 모은 이웃 정보와 노드 자신의 현재 정보를 합친다. 그리고 이 합쳐진 정보를 선형 변환(가중치 행렬 곱하기)과 활성화 함수(ReLU 등)에 통과시켜 새로운 정보로 갱신한다.
이 과정을 여러 레이어에 걸쳐 반복한다. 1개의 GNN 레이어를 통과하면 각 노드는 이웃(1-hop)의 정보를 갖게 된다. 2개의 레이어를 통과하면 이웃의 이웃(2-hop) 정보까지 반영되어, 점점 더 넓은 범위의 그래프 문맥을 파악하게 된다.
Graph Representation
컴퓨터한테 그래프는 어떻게 알려줘야할까?
컴퓨터는 그림을 못 보니까, 그래프를 행렬(matrix)로 바꿔서 알려줘야 한다. 보통 아래의 세 가지를 사용
- 인접 행렬(Adjacency Matrix, A): "누가 누구랑 연결됐는지" 알려주는 행렬. 노드 N개가 있으면 NxN 크기 행렬을 만들고, 노드 i와 j가 연결돼 있으면 1, 아니면 0을 적는다.
- 이 인접 행렬을 제곱하면(A^2) "두 다리 건너 아는 사이"(길이 2의 경로)를 알 수 있다. (5pg 참고)
- 노드 특징 행렬(Node feature matrix, X): 각 노드가 가진 특징이나 속성을 담은 행렬
- 엣지 특징 행렬(Edge feature matrix, E): 엣지 자체가 특징을 가질 떄 사용
- 예를 들어 지하철 노선도에서 엣지(노선)는 거리, 소요 시간 같은 특징을 가진다.
GNN의 가장 중요한 특징!
그래프에서는 노드 번호를 1,2,3으로 매기든 3,1,2로 매기든 순서가 상관없다. 그래프 본질은 안 바뀌니까. 이걸 순열 불변성(Permutation Invariance)라고 하는데, GNN은 이 성질을 만족하도록 설계돼야 한다. 이게 GNN을 특별하게 만드는 핵심 중 하나!
GNN 주요 task 3가지
GNN을 이용해 풀 수 있는 문제는 크게 3가지로 나뉜다.
- 그래프 (Graph-level): 그래프 전체에 대한 예측
- 예시: "이 분자 구조(그래프)는 독성이 있는가?"
- 방법: GNN을 통과한 모든 노드의 최종 정보를 평균 내는 등 하나의 벡터로 합친 뒤, 분류기로 예측
- 노드 (Node-level): 각 노드에 대한 예측
- 예시: "소셜 네트워크의 이 사용자는 봇인가, 사람인가?"
- 방법: GNN을 통과해 문맥 정보가 풍부해진 각 노드의 최종 정보를 보고 개별적으로 분류한다.
- 링크 예측(Edge-level): 두 노드 사이에 연결(엣지)이 생길지 예측
- 예시: "이 두사람에게 친구 추천을 해줘야 할까?"
- 방법: 두 노드의 최종 정보 벡터를 내적(dot product)하는 등의 방법으로 연결 확률을 계산.
Inductive vs. Transductive: GNN만의 독특한 학습 환경
GNN은 다른 모델과 다른 독특한 학습 환경을 가지는데,
- Inductive 학습: 우리가 흔히 아는 방식. 여러개의 학습용 그래프로 모델을 학습시킨 뒤, 완전히 새로운, 처음 보는 테스트용 그래프에 대해 예측한다. 분자 독성 예측이 대표적인 예시.
- Transductive 학습: 거대한 그래프 하나만 주어진다. 이 그래프의 일부 노드에만 라벨이 있고, 나머지 노드의 라벨은 비어있다. 모델은 라벨이 있는 노드를 이용해 학습하고, 같은 그래프 내의 라벨 없는 노드들을 예측한다. 소셜 네트워크에서 일부 유저 정보를 바탕으로 다른 유저의 성향을 예측하는 경우가 여기에 해당한다.
거대한 단일 그래프로 학습하는 Transductive 방식 때문에, 전체 그래프를 메모리에 올릴 수 없어 이웃 샘플링이나, 그래프 분할 같은 기술로 미니배치를 만들어 학습하는 기법이 발전했다.
GNN을 더 강력하게 만드는 Advanced Topics
- Aggregation Methods
- 다양한 정보 집계 방식
- 이웃 정보를 단순히 더하는 것 말고, 평균을 내거나(Mean Aggregation), 최대값을 뽑거나(Max Pooling), 더 복잡한 정규화(Kipf Normalization)를 하는 등 여러 variation이 있다.
- Graph attention network
- 모든 이웃이 똑같이 중요하진 않잖아? 라는 아이디어
- 트랜스포머의 어텐션처럼, 어떤 이웃의 정보에 더 집중할지 가중치를 학습해서 더 중요한 정보에 힘을 실어주는 방식.
- 성능이 아주 좋다
- 거대 그래프 다루기
- facebook 같은 수십억 노드 그래프를 통째로 학습시키는 건 불가능하다. 그래서 필요한 부분만 샘플링해서 작은 그래프를 만들어 학습하거나(Neighborhood Sampling), 그래프를 여러 덩어리로 쪼개서(Graph Partitioning) 처리하는 등의 기법을 사용한다.
트랜스포머 사촌 GNN
GNN의 이웃 정보 수집(aggregation) 방식을 단순히 더하는 것 말고, "어떤 이웃이 더 중요할까?"를 학습해서 가중치를 다르게 주면 어떨까? 이게 바로 위에서 언급한 GAT다. - 트랜스포머: 모든 단어가 모든 다른 단어에 어텐션을 적용 - GAT: 각 노드가 자신의 이웃 노드들에 대해서만 어텐션을 적용. 인접행렬(그래프 구조)에 의해 어텐션을 계산할 범위가 제한됨
이처럼 GNN은 트랜스포머의 어텐션 메커니즘을 그래프 구조에 맞게 변형하여 적용한, 매우 밀접한 관계의 모델이라고 볼 수 있겠다.
정리
- GNN은 관계와 구조를 가진 그래프 데이터를 위한 딥러닝이다.
- 핵심 원리는 "주변 노드의 정보를 모아서 내 정보를 업데이트"하는 메시지 패싱이다.
- 이 과정을 반복하면 더 넓은 범위의 관계를 학습할 수 있다.
- 이를 통해 그래프 전체, 개별 노드, 노드 간의 연결에 대한 다양한 예측이 가능하다.
용어
- 노드: 점
- 엣지: 선(노드 사이의 관계)
화이팅