논문 정보: Waikhom, L., & Patgiri, R. (2021). Graph neural networks: Methods, applications, and opportunities. arXiv preprint arXiv:2108.10733.
인용수: 80회 (25.07.26 기준)
특이사항: 이 논문은 GNN 방법론 전반에 대한 survey 논문
1. GNN의 기초
그래프란 무엇인가?
그래프는 노드(node)와 엣지(edge)로 구성된 자료구조임
- 노드: 개체나 객체 (예: 사람, 단어, 원자)
- 엣지: 개체 간의 관계나 연결 (예: 친구 관계, 단어 간 관련성, 화학 결합)
그래프의 특징
- 비유클리드 구조: 이미지나 텍스트와 달리 고정된 격자 구조가 없음
- 가변적인 이웃 수: 각 노드마다 연결된 이웃의 수가 다름
- 순열 불변성: 노드의 순서가 바뀌어도 그래프는 동일함
기존 딥러닝과의 차이
- CNN (이미지): 3×3 필터가 규칙적인 격자를 슬라이딩
- RNN (텍스트): 순차적으로 단어를 하나씩 처리
- GNN (그래프): 각 노드의 이웃이 다르므로 새로운 접근 필요
GNN의 수학적 기초
그래프 G = (V,E)는 다음과 같이 표현
- V = {v₁, v₂, ..., vₙ}: 노드 집합
- E ⊆ V × V: 엣지 집합
- A ∈ ℝⁿˣⁿ: 인접 행렬 (Aᵢⱼ = 1 if (vᵢ, vⱼ) ∈ E)
- X ∈ ℝⁿˣᵈ: 노드 특징 행렬 (각 노드는 d차원 특징 벡터)
GNN의 핵심은 Message Passing(각 노드는 이웃들로부터 메시지를 받아 자신의 representation을 업데이트)
1단계 - 메시지 계산: $ m_{ij}^{(k)} = Message(h_i^{(k-1)}, h_j^{(k-1)}, e_{ij}) $
2단계 - 메시지 집계: $m_i^{(k)} = Aggregate({m_{ij}^{(k)} : j ∈ N(i)})$
3단계 - 노드 업데이트: $h_i^{(k)} = Update(h_i^{(k-1)}, m_i^{(k)})$
가장 대표적 GNN 모델인 Graph Convolutional Networks(GCN) 레이어는 다음과 같이 정의됨
$ H^{(l+1)} = σ(D̃^{-1/2}ÃD̃^{-1/2}H^{(l)}W^{(l)}) $
여기서:
- Ã = A + I: self-loop가 추가된 인접 행렬
- D̃: Ã의 degree 행렬
- $ W^{(l)} $: 학습 가능한 가중치 행렬
- σ: 활성화 함수
2. 학습 패러다임별 상세 분석
지도 학습(Supervised Learning)
주요 특징:
- 모든 노드/엣지/그래프에 레이블이 존재
- 직접적인 손실 함수 최적화 가능
- 주로 분류나 회귀 문제에 활용
대표적 방법론:
- GBILI (Graph-based on Informativeness of Labeled Instances): 레이블 정보를 활용한 그래프 구축
- RGCLI (Robust Graph that Considers Labeled Instances): GBILI의 개선 버전으로 더 강건한 그래프 생성
비지도 학습(Unsupervised Learning)
1) Graph Auto-encoders
원리: 그래프 구조를 저차원 표현으로 인코딩한 후 다시 복원
주요 모델들:
- GAE/VGAE (Kipf & Welling, 2016):
- GCN을 인코더로 사용
- 인접 행렬 재구성을 통한 학습
- 변분 추론을 통한 확률적 임베딩
- MGAE (Marginalized GAE):
- 노이즈 제거 오토인코더 사용
- 더 강건한 노드 표현 학습
- GALA (Graph convolutional Auto-encoder using Laplacian):
- 라플라시안 smoothing과 sharpening 활용
- 대칭적 구조의 오토인코더
2) Contrastive Learning
원리: 유사한 샘플은 가깝게, 다른 샘플은 멀게 표현 학습
주요 모델들:
- DGI (Deep Graph Infomax):
- 전역 그래프 표현과 로컬 노드 표현 간 상호정보 최대화
- 노이즈를 추가한 negative 샘플 생성
- InfoGraph:
- 그래프 레벨과 서브구조(노드, 엣지, 삼각형) 레벨 간 상호정보 최대화
- 다양한 스케일의 구조 정보 포착
- MVGRL (Multi-view Representation Learning):
- 그래프 diffusion과 원본 구조를 서로 다른 view로 활용
- Cross-view 상호정보 최대화
3) Random Walk 기반 방법
한 노드에서 시작하여 연결된 이웃 중 무작위로 선택해서 반복적으로 이동하여 경로 생성
예시: A - B - D - C - B - A
자주 함께 나타나는 노드들은 비슷한 특성을 가질 가능성이 높음 - 이를 통해 노드의 "맥락" 파악
원리: 랜덤 워크를 통해 노드의 구조적 유사성 포착
주요 모델들:
- DeepWalk:
- 랜덤 워크를 "문장"으로, 노드를 "단어"로 간주
- Skip-gram 모델 활용
- Node2Vec:
- BFS와 DFS를 조절하는 파라미터 p, q 도입
- Homophily와 structural equivalence 균형
- 동질적인 노드 뿐만 아니라 그래프 전체에서 비슷한 역할을 하는 구조적 동등성까지 모두 학습 가능
Homophily: 비슷한 노드(같은 무리 등)끼리 연결되는 경향 - 동질성
Structural Equivalence - 구조적 동등성
준지도 학습 (Semi-supervised Learning)
1) Shallow Embedding
특징: 각 노드마다 독립적인 임베딩 벡터 학습
Factorization 기반:
- 행렬 분해를 통한 노드 임베딩
- Laplacian Eigenmaps, GraRep 등
Random Walk 기반:
- LINE: 1차 및 2차 근접성 보존
- PTE: 이질적 텍스트 네트워크용
한계점:
- 파라미터 공유 없음 (O(|V|) 파라미터)
- 노드 특징 활용 불가
- Inductive learning 불가능
2) Deep Embedding
특징: 신경망을 통한 파라미터 공유
Auto-encoder 기반:
- SDNE: 딥 오토인코더 활용
- DNGR: random surfing을 통한 PPMI 행렬 구성
GNN 기반:
- 구조와 특징 정보 동시 활용
- Inductive learning 가능
- 파라미터 효율성
Inductive Learning: 학습 시 보지 못한 노드도 처리 가능
Transductive Learning: 학습 시 본 노드만 처리 가능
자기지도 학습(Self-supervised Learning)
1) Pretext Tasks 분류
Pretext Task란 실제 목표(Downstream Task)를 위한 좋은 표현을 학습하기 위해 설계된 보조 작업(auxiliary work)
(1) Masked Feature Regression (MFR)
- 노드/엣지 특징을 마스킹하고 복원
- 컴퓨터 비전의 image inpainting에서 영감
- 예: 노드 특징의 일부를 0으로 마스킹 후 복원
(2) Auxiliary Property Prediction (APP)
- Regression 기반:
- NodeProperty: 노드 차수 예측
- Distance2Cluster: 클러스터까지 거리 예측
- PairwiseAttrSim: 노드 쌍의 특징 유사도 예측
- Classification 기반:
- M3S: DeepCluster를 활용한 pseudo-label 생성
- Node Clustering: 사전 계산된 클러스터 인덱스 활용
(3) Same-Scale Contrasting (SSC)
- Context 기반:
- 랜덤 워크상 가까운 노드는 positive pair
- Homophily 가정 활용
- Augmentation 기반:
- GCC: 랜덤 워크 기반 서브그래프 증강
- GRACE: 노드 특징과 엣지 마스킹
(4) Cross-Scale Contrasting (CSC)
- 서로 다른 스케일 간 대조 학습
- 노드-서브그래프, 노드-그래프 대조
- DGI, Subg-Con 등
2) 학습 전략
- Joint Learning: Pretext와 downstream task 동시 학습
- Pre-training & Fine-tuning: 2단계 학습
- Unsupervised Representation Learning: 고정된 인코더로 downstream task 학습
3. GNN 아키텍쳐 설계 가이드
1) 그래프 구조 식별
구조적 시나리오: 분자, 소셜 네트워크 등 명시적 그래프 비구조적 시나리오: 텍스트, 이미지에서 그래프 구축 필요
2) 그래프 타입 결정
- 방향성: 정보 흐름의 방향이 중요한가?
- 이질성: 노드/엣지 타입이 다양한가?
- 동적성: 시간에 따라 변화하는가?
- 가중치: 엣지에 강도 정보가 있는가?
3) 계산 모듈 구성
Propagation Module:
- Spectral 방법: 주파수 도메인에서 convolution
- Spatial 방법: 이웃 aggregation
- Attention 메커니즘: 이웃의 중요도 학습
Sampling Module:
- GraphSAINT: 서브그래프 샘플링
- FastGCN: 레이어별 노드 샘플링
- Cluster-GCN: 클러스터 기반 미니배치
Pooling Module:
- DiffPool: 미분 가능한 풀링
- SAGPool: Self-attention 기반 풀링
- TopKPool: Top-k 노드 선택
4.주요 데이터셋과 벤치마크
1) Citation Networks
- Cora: 2,708 노드, 7개 클래스, ML 논문
- CiteSeer: 3,327 노드, 6개 클래스
- PubMed: 19,717 노드, 당뇨병 관련 논문
2) Social Networks
- Reddit: 232,965 포스트, 41개 서브레딧
- Facebook: 4,039 사용자, 친구 관계
- Flickr: 1.7M 사용자, 5개 관심사 그룹
3) Biochemical Networks
- PPI: 단백질 상호작용, 121개 GO 레이블
- MUTAG: 화학 화합물, 변이원성 예측
- QM9: 134k 분자, 19개 양자 화학적 특성
5. 이론적 분석
1) 표현력 (Expressivity)
- WL-test 한계: 대부분의 GNN은 1-WL test와 동등
- 고차 GNN: k-WL test 수준의 표현력 달성 가능
- 한계: 사이클 카운팅, 그래프 지름 등 전역 특성 학습 어려움
2) 일반화 (Generalization)
- VC dimension과 Rademacher complexity 분석
- 그래프 크기에 대한 일반화 경계
- Spectral filter의 안정성 조건
3) Over-smoothing 문제
- 레이어가 깊어질수록 노드 표현이 구별 불가능해짐
- Laplacian smoothing의 반복 적용으로 해석
- 해결책: Skip connection, DropEdge, PairNorm 등
6. 미해결 과제와 연구 방향
1) 확장성 (Scalability)
문제점:
- 전체 그래프를 메모리에 로드
- 이웃 수 폭발적 증가
- 미니배치 구성의 어려움
해결 방향:
- 효율적인 샘플링 전략
- 분산 학습 프레임워크
- 그래프 전용 하드웨어
2) 동적 그래프
문제점:
- 시간에 따른 구조 변화
- 연속 시간 모델링
- 효율적인 업데이트
해결 방향:
- Temporal attention 메커니즘
- 증분 학습 방법
- 메모리 네트워크 활용
3) 설명가능성
문제점:
- Black-box 모델
- 예측 근거 불명확
- 신뢰성 문제
해결 방향:
- Attention 시각화
- Subgraph 중요도 분석
- Counterfactual 설명
4) 강건성과 공정성
문제점:
- 적대적 공격 취약성
- 노드/엣지 perturbation
- 편향된 예측
해결 방향:
- 인증된 강건성
- 공정성 제약 조건
- Debiasing 기법
7. 실무 활용을 위한 제언
1) 모델 선택 가이드
- 작은 그래프 + 풍부한 특징: GAT, GIN
- 큰 그래프 + 희소 특징: GraphSAGE, FastGCN
- 동적 그래프: EvolveGCN, TGAT
- 이질적 그래프: HAN, HGT
2) 구현 팁
- 정규화의 중요성 (node features, adjacency matrix)
- Early stopping과 patience
- Learning rate scheduling
- Negative sampling 전략
3) 평가 지표
- 노드 분류: Accuracy, F1-score
- 링크 예측: AUC, AP
- 그래프 분류: Accuracy, AUC
- 클러스터링: NMI, ARI
