공통 정의
COMMON DEFINITIONS
그래프 신경망(GNN)은 그래프 구조 데이터 위에서의 학습을 위해 설계된 딥러닝 모델 부류다. 본격적인 논의에 앞서 핵심 정의들을 제시한다.
그래프는 튜플 G = (V, E)로 정의된다. V = {v1, …, vN}은 N개 노드의 집합, E = {e1, …, eM}은 노드 쌍을 연결하는 M개 간선의 집합이며 통상 e = (vi, vj)는 vi에서 vj로의 간선을 나타낸다. 그래프는 유향 또는 무향일 수 있고, 인접행렬로 동등하게 표현되는 경우가 많다.
각 노드·간선에는 그 특성을 기술하는 속성 벡터가 부여될 수 있다. 노드 특징은 통상 행렬 XV ∈ ℝN×d(노드마다 d차원 벡터), 간선 특징은 XE ∈ ℝM×d로 표현된다. 예컨대 소셜 네트워크에서 노드 특징은 사용자 프로필을, 간선 특징은 소통 빈도나 관계 유형을 인코딩할 수 있다.
GNN의 핵심 계산 과정은 메시지 패싱(이웃 집계) 메커니즘이다. 각 대상 노드는 이웃들로부터 메시지(특징)를 집계하고, 학습 가능한 집계 함수로 자신의 표현을 갱신한다. 여기서 𝒩(v)는 노드 v의 이웃 집합, AGG는 집계 함수(평균, 가중합, 어텐션 등), σ는 비선형 활성 함수, W(k), b(k)는 k번째 레이어의 학습 가능 파라미터다.
GNN 학습은 순전파, 손실 계산, 그래디언트 기반 역전파로 이루어져 전통적 신경망과 유사하다. 핵심적 차이는 반복(iteration)마다 계산 그래프가 동적으로 구성된다는 점이다. 각 대상 노드에 대해 K-hop 이웃을 회수하여 — 그래프를 트리로 펼치듯 — 계산 서브그래프를 형성하고, 그 위에서 다층 집계를 수행한 뒤 손실 계산과 파라미터 갱신이 이어진다.
실세계 그래프는 대개 대규모이므로 배치마다 전체 그래프를 처리하는 것은 비현실적이다. 이에 학습 시스템은 대상 노드 집합으로부터 고정 수의 이웃을 (무작위 또는 중요도 기반으로) 샘플링하여 학습용 서브그래프를 구성하는 전략을 채택한다. 샘플링은 배치당 계산량과 메모리 사용량을 크게 줄인다.
대상 노드가 이웃으로부터 정보를 모으는 과정으로, 통상 선형 변환 후 합·평균·어텐션 가중 집계가 뒤따른다. GCN[1]은 인접행렬의 대칭 정규화로 합성곱을 수행하고, GAT[2]는 이웃에 학습 가능한 어텐션 가중치를 부여한다. 집계 함수의 선택은 모델의 표현력과 계산 효율에 직접적 영향을 미친다.
GNN 학습은 특히 고차수(high-degree) 노드를 가진 대규모 그래프에서 메모리 집약적이다. 일반적인 최적화로는 반복당 메모리 부담을 줄이는 레이어 단위·서브그래프 샘플링, 그리고 중간 결과 재사용을 위한 비동기 I/O와 메모리 캐싱 전략이 있으며, 이후 절에서 단일·다중 GPU 시나리오별로 상세히 다룬다.
정적 그래프 위의 GNN
GRAPH NEURAL NETWORKS ON STATIC GRAPHS
2.2.1풀그래프 학습
N개 노드 집합 𝒱와 간선 집합 ℰ ⊆ 𝒱 × 𝒱로 이루어진 그래프 𝒢 = (𝒱, ℰ)에서, 위상 연결은 대칭 인접행렬 A로 표현된다(Aij = 1이면 간선 존재). 효과적인 메시지 패싱을 위해 GCN[3] 같은 널리 쓰이는 모델은 대칭 정규화 인접행렬을 사용한다 — Â = D̄−1/2ĀD̄−1/2, 여기서 Ā = A + IN은 각 노드에 셀프루프를 더한 것이고 D̄는 Ā로부터 유도된 대각 차수 행렬이다.
행렬 연산 관점에서 GNN의 ℓ번째 레이어 특징 전파는 H(ℓ) = σ(H(ℓ−1), Â; W(ℓ−1))로 일반화된다[4, 5]. H(0) = X ∈ ℝN×F는 초기 입력(각 행이 노드의 특징 벡터), W는 학습 가능 가중치 행렬, σ는 비선형 활성 함수(예: ReLU)다. 학습은 두 국면으로 진행된다.
순전파 국면 (Forward Phase)
이웃 정보를 집계하고 선형 변환을 적용한다.
역전파 국면 (Backward Phase)
연쇄 법칙으로 그래디언트를 재귀적으로 계산해 파라미터를 갱신한다. 손실 ℒ에 대한 중간 표현 Z(ℓ)의 오차항을 δ(ℓ) = ∇Z(ℓ)ℒ라 하면, 오차 전파와 가중치 그래디언트는 다음과 같다(⊙는 성분별 곱, σ′는 활성 함수의 도함수).
하나의 학습 에폭은 이 순전파·역전파로 구성되며, 학습률 η를 사용한 파라미터 최적화 단계 W(ℓ−1) ← W(ℓ−1) − η∇W(ℓ−1)ℒ (Eq 2.7)로 마무리된다. 학습은 모델이 수렴할 때까지 반복된다. 위 정식화는 풀배치 학습에 전형적인 행렬 중심 관점이지만, 현대적 접근 — 특히 정교한 GNN 아키텍처나 샘플링 기반 학습 전략 — 은 이 과정을 메시지 패싱의 렌즈로 해석하는 경우가 많다[6, 7].
2.2.2미니배치 학습
대규모 그래프에서 풀배치 학습이 갖는 태생적 확장성 한계는 GraphSAGE[8]가 개척한 미니배치 전략의 채택으로 이어졌다. 전체 그래프 위상을 한꺼번에 처리하는 대신 샘플링된 서브그래프 위에서 동작하며, 각 반복마다 특정 대상 노드 집합의 예측에 필요한 국소 구조 맥락과 특징 정보를 담은 미니배치를 구성한다. fanout {2, 2}의 2-레이어 GraphSAGE로 노드 12를 대상 삼는 경우(Fig 2.1), 미니배치 생성은 두 국면으로 이루어진다.
Adj-Sampling — 구조 샘플링
시스템이 그래프 구조를 재귀적으로 순회한다. 대상 노드 12에서 출발해 인접 리스트에 접근하여 이웃(예: 노드 6과 81)을 무작위 선택하고, 다음 레이어에서 이를 반복한다. 샘플러가 그래프 위상을 따라 포인터를 추적하므로 무작위적이고 세밀한(fine-grained) 메모리 접근이 특징이다.
Nfeat-Selecting — 특징 추출
계산 서브그래프가 확정되면 관련된 모든 노드의 인덱스를 수집하고, 해당 특징 벡터를 벌크(bulk) 회수한다. 흩어진 접근 패턴의 구조 샘플링과 달리, 특징 추출은 통상 더 조밀하고 고처리량의 메모리 연산이 가능하다.
완료되면 샘플링된 구조와 수집된 특징이 하나의 미니배치로 패키징되고, 모델은 노드 12에 대한 손실 계산, 역전파, 가중치 갱신을 수행한다. 표준 구현 패러다임에서는 CPU가 데이터 집약적 준비 작업(Adj-Sampling, Nfeat-Selecting)을 맡아 결과를 호스트 메모리에 저장하고, 준비된 미니배치가 PCIe 버스를 거쳐 계산 집약적 모델 학습을 담당하는 GPU로 전송된다.
GraphSAGE의 노드 단위 이웃 샘플링을 넘어 연구 공동체는 폭넓은 샘플링 방법론을 발전시켜 왔으며, 크게 노드 단위, 레이어 단위, 서브그래프 단위로 분류된다.
노드 단위 샘플링
집계 과정에서 각 노드의 이웃 부분집합을 샘플링한다. 레이어마다 고정 수의 이웃(fanout)을 무작위 샘플링하고, 샘플링된 이웃에 대해서만 집계를 수행한다. 대표작은 GraphSAGE[8](귀납적 표현 학습의 일반 프레임워크)와, 중요도 기반 샘플링으로 영향력 높은 노드를 우선하는 그 확장 PinSage[9]다.
＋ 구현이 단순하고 계산 효율적, 고차수 노드가 많은 대규모 그래프에 적합
− 핵심 이웃 누락 시 구조 정보 손실, 그래디언트 분산 증가로 수렴 저해, 모델 깊이 k에 대해 배치 크기가 O(10k)로 지수 증가(fanout 10 기준) — 깊은 GNN으로의 확장성 제약
레이어 단위 샘플링
레이어마다 독립적으로 샘플링 제약을 부과하여 레이어 간 샘플 노드 수를 일정하게 유지하고, 모델 깊이에 대한 지수적 증가를 회피한다. 분산·연결성·손실 기여도를 고려해 각 레이어에서 노드 부분집합을 독립 샘플링하고, 레이어를 잇는 경로 위에서만 집계한다. FastGCN[10]은 레이어별 노드 샘플링을 중요도 샘플링 문제로 취급하되 레이어 간 연결성이 희생되기 쉽고, LADIES[11]는 인접행렬 기반 샘플링으로 샘플 노드 간 연결성과 그래프 구조를 보존해 이를 개선한다.
＋ 레이어별 독립 샘플링으로 중복 감소, 이웃 폭발 회피로 깊은 GNN에서 효율적
− 핵심 노드 누락 시 구조 정보 손실 여전, 중요도 샘플링의 부가 오버헤드가 실제 GNN 학습 계산을 능가할 수도 있음[12, 13]
서브그래프 단위 샘플링
원본 그래프에서 서브그래프 전체를 샘플링하고 그 위에서만 계산한다. ClusterGCN[14]은 그래프 클러스터링으로 노드를 조밀 클러스터들로 분할한 뒤, 학습 단계마다 클러스터를 무작위로 골라 결합해 미니배치로 쓴다 — 다만 대규모·조밀 그래프에서 분할/클러스터링 비용이 커서 전처리 시간이 이후 모델 학습 시간을 초과할 수 있다. GraphSAINT[12]는 샘플링된 노드/간선으로부터 서브그래프를 유도(induce)하고, 샘플링 빈도에 대한 비편향성과 구조 보존을 위해 정규화·분산 축소 기법을 도입한다.
＋ 서브그래프 내 국소 구조 보존, 샘플 간 독립성으로 미니배치·분산 계산에 적합, 메모리 사용 절감
− 클러스터링·파티셔닝 비용이 클 수 있음, 전역 구조 미보존 시 편향(bias) 유입 가능
| 비교 축 | 노드 단위 | 레이어 단위 | 서브그래프 단위 |
|---|---|---|---|
| 동작 수준 (granularity) | 노드 수준 | 레이어 수준 | 그래프 수준 |
| 핵심 문제 대응 | 레이어별 이웃 수 고정 — 깊은 모델에서 이웃 폭발 발생 | 레이어별 총 샘플 수 제한으로 이웃 폭발 해소 | 국소 구조를 더 보존하며 이웃 폭발과 고비용 레이어 샘플링을 모두 회피 |
| 샘플링 오버헤드 | 가장 낮음 | 추가 전처리 부담 발생 가능 | 추가 전처리 부담 발생 가능 |
| 대표 기법 | GraphSAGE · PinSage | FastGCN · LADIES | ClusterGCN · GraphSAINT |
※ 세 방식 모두 그래프의 부분집합 샘플링으로 GNN 학습 계산 비용을 줄인다는 공통 목표를 가지며, 방식의 선택은 응용, 그래프 크기, 효율–정확도 트레이드오프에 따라 달라진다.
2.2.3GNN의 주요 태스크와 데이터셋
GNN은 노드 분류, 링크 예측, 그래프 분류를 포함한 광범위한 태스크에 성공적으로 적용되어 왔다. 각 태스크는 그래프 분석의 서로 다른 도전과제를 다루며 벤치마킹·평가를 위한 고유의 데이터셋을 활용한다.
① 노드 분류 (Node Classification)
노드의 특징과 그래프 구조에 기반해 노드의 레이블·범주를 예측하는 그래프 분석의 근본 태스크다. 소셜 네트워크 분석, 추천 시스템, 생물정보학 등에서 널리 쓰인다.
| 데이터셋 | 도메인 | 노드 | 간선 | 특징 차원 | 클래스 |
|---|---|---|---|---|---|
| Cora[15] | 인용 네트워크 (과학 문헌) | 2,708 | 5,429 | 1,433 (이진 단어 존재) | 7 |
| Citeseer[15] | 인용 네트워크 | 3,327 | 4,732 | 3,703 | 6 |
| PubMed[15] | 생의학 문헌 인용 | 19,717 | 44,338 | 500 (TF-IDF) | 3 |
| Reddit[14] | 소셜 네트워크 (게시물 상호작용) | 232,965 | 11,606,919 | 602 | 41 (커뮤니티) |
② 링크 예측 (Link Prediction)
노드 쌍 사이 간선(링크)의 존재를 예측한다. 추천 시스템, 지식 그래프 완성, 소셜 네트워크 분석에 핵심적이다.
| 데이터셋 | 도메인 | 노드 | 간선 | 예측 대상 |
|---|---|---|---|---|
| Facebook[16] | 소셜 네트워크 | 4,039 (사용자) | 88,234 (친구관계) | 누락된 친구관계 |
| PPI[17] | 생물학 네트워크 | 3,852 (단백질) | 37,841 (상호작용) | 잠재적 단백질 상호작용 |
| BlogCatalog[18] | 소셜 네트워크 | 10,312 (블로거) | 333,983 (친구관계) | 누락된 사회적 연결 |
| UCI Message[19] | 커뮤니케이션 네트워크 | 1,899 (사용자) | 20,296 (메시지) | 미래의 사용자 간 상호작용 |
③ 그래프 분류 (Graph Classification)
그래프 전체의 레이블·속성을 예측한다. 분자 속성 예측, 소셜 네트워크 분석, 화합물 분류 등에 필수적이다.
| 데이터셋 | 도메인 | 그래프 수 | 레이블 | 분류 과제 |
|---|---|---|---|---|
| MUTAG[20] | 화합물 (분자) | 188 | 7종 이산 레이블 | 박테리아에 대한 돌연변이 유발성(mutagenic effect) 분류 |
| PROTEINS[21] | 단백질 구조 | 1,113 | 2 | 효소 / 비효소 분류 |
| NCI1[22] | 화합물 (분자) | 4,110 | 2 | 비소세포폐암에 대한 활성 여부 분류 |
| IMDB-BINARY[23] | 영화 협업 (배우 에고 네트워크) | 1,000 | 2 | 영화 장르(액션/코미디) 분류 |
2.2.4희소 그래프 표현과 저장
표준 그래프 데이터셋은 두 개의 주요 데이터 구조 — 위상을 나타내는 인접행렬과 노드 속성을 나타내는 특징 행렬 — 로 구성된다. 노드 특징은 통상 조밀(dense)하여 (N, f) 형태의 연속 2차원 텐서로 효율적으로 관리할 수 있는 반면(N: 노드 수, f: 특징 차원), 위상 데이터에는 더 특수한 처리가 필요하다.
실세계 그래프는 상당한 희소성(sparsity)을 보이므로 조밀 행렬 저장은 비현실적이다. 이에 COO(Coordinate List), CSR(Compressed Sparse Row), CSC(Compressed Sparse Column) 같은 압축 포맷이 그래프 처리의 표준이며, GNN 학습 — 특히 GraphSAGE[8]류의 샘플링 기반 프레임워크 — 맥락에서는 CSC가 PyG[24], DGL[25] 같은 시스템이 채택한 사실상의 표준이 되었다. CSC는 인접행렬을 세 개의 선형 배열로 압축한다.
⟨Fig 2.2⟩ CSC 포맷으로 저장된 인접행렬. col_ptr는 인덱스 맵, row_idx는 in-neighbor(들어오는 간선의 출발 노드) 목록, values는 선택적 간선 가중치·속성이다.
GNN 시스템에서 CSC가 지배적인 이유는 메시지 패싱 국면의 알고리즘적 요구 때문이다. GNN은 통상 노드의 들어오는 이웃(in-neighbor)으로부터 정보를 집계하므로, CSC 레이아웃은 대상 노드의 모든 in-neighbor가 메모리에 연속적으로 저장됨을 보장한다. 이 공간 지역성은 성능에 결정적이며, 무작위 메모리 접근을 최소화하고 대역폭 활용을 극대화하는 고도로 최적화된 C++·CUDA 샘플링 커널의 개발을 가능하게 한다.
동적 그래프 위의 GNN
GRAPH NEURAL NETWORKS ON DYNAMIC GRAPHS
이 절은 진화하는 그래프 구조 위에서의 학습을 위한 이론적 기초를 세운다. 연속 시간 동적 그래프(CTDG)를 형식적으로 정의하고, 시간적 GNN(T-GNN)의 아키텍처를 소개하며, 대규모 데이터셋에서 이들 모델을 학습하는 표준 파이프라인을 기술한다.
2.3.1연속 시간 동적 그래프 (CTDG)
CTDG는 시간 순서 t1 ≤ t2 ≤ …로 정렬된, 타임스탬프가 부여된 상호작용 이벤트의 스트림 𝒢 = {α(t1), α(t2), …}로 형식화된다. 각 상호작용 이벤트는 튜플 α(t) = (vi, vj, eij(t), t)로 캡슐화되며, vi·vj는 상호작용의 출발·도착 노드, t는 정확한 타임스탬프, eij(t)는 해당 시간적 간선의 속성을 인코딩하는 특징 벡터다.
구조적으로 CTDG는 임의의 노드 쌍 (vi, vj) 사이에 타임스탬프와 특징 속성으로 구별되는 다수의 동시적·순차적 간선을 허용하는 시간적 멀티그래프(temporal multigraph)로 기능한다. 이산 시간 동적 그래프(DTDG) 대신 CTDG에 초점을 두는 이유는 실세계 현상 모델링에서의 우월한 충실도(fidelity) 때문이다. 이벤트를 성긴(coarse-grained) 스냅숏으로 집계하는 DTDG와 달리 CTDG는 상호작용의 정확한 타이밍을 보존하며, 이 세밀함은 불규칙한 시간 패턴과 동적 시스템 고유의 연속적 진화를 포착하는 더 표현력 있는 프레임워크를 제공한다[26–30].
CTDG는 단순한 상호작용 추가를 넘어 풍부한 시간적 이벤트 스펙트럼을 포착한다. 연관된 기술(descriptive) 특징의 변화를 통해 반영되는 이벤트 삭제·갱신[31]이 포함되며, 노드 추가·삭제·특징 갱신 같은 노드 수준 이벤트도 셀프 상호작용 이벤트(출발과 도착이 같은 노드인 간선)로 자연스럽게 표현할 수 있어, 정의 1의 동일한 시간적 이벤트 정식화로 통일적으로 기술된다.
2.3.2시간적 그래프 신경망 (T-GNN)
T-GNN은 동적 그래프에 대한 표현 학습에서 강력한 능력을 입증해 왔다. CTDG를 위한 기존 최신 T-GNN들[27, 28, 30]은 대체로 두 핵심 컴포넌트 — 노드 상태 갱신과 시간적 메시지 패싱 — 로 이루어진 통일된 아키텍처 패러다임을 따른다.
노드 상태 갱신 (Node State Update)
노드마다 상호작용 이력의 길이가 다르므로, 이웃 샘플링만으로는 장기 시간 의존성을 포착하기 어렵다. 이에 대부분의 T-GNN 모델[27, 29, 30, 32]은 각 노드의 과거 상호작용 정보를 인코딩한 상태 벡터를 보관하는 전용 메모리 모듈을 유지한다. 노드 vi의 상태 벡터 si(t)는 시점 t까지의 시간적 맥락을 요약하며, 새 상호작용 α(t) = (vi, vj, eij(t), t)가 도착하면 양쪽 노드의 상태가 갱신된다.
UPDATE는 통상 RNN 또는 GRU 모듈로 구현되며, φ(·)는 경과 시간 Δt = t − t−를 벡터 표현으로 변환하는 시간 인코딩 함수다(vj도 대칭적으로 갱신).
시간적 메시지 패싱 (Temporal Message Passing)
새 상호작용 α(t)가 발생하면 모델은 노드 vi(와 vj)에 대한 시간적 임베딩 hi(t)를 다음 절차로 생성한다.
SAMPLE은 시점 t 이전에 vi가 참여한 과거 상호작용을 선택하는 시간적 이웃 샘플링을 수행한다. 시간적 샘플링은 타임스탬프를 고려하므로 같은 노드가 서로 다른 시점에서 여러 번 샘플링될 수 있으며, 상호작용 시각 기준으로 가장 최근 k개의 이웃을 회수하는 top-k 최근 이웃 샘플링[27, 29, 32]이 일반적 전략이다. AGGREGATE는 흔히 어텐션 메커니즘으로 구현되어 각 레이어(ℓ = 1, …, L)의 임베딩을 산출한다. 첫 레이어(ℓ = 0)의 입력은 노드의 현재 상태 벡터와 (가용한 경우) 정적 특징 xj로 구성되며, 초기 노드 특징이 없으면 상태 벡터만 사용한다.
2.3.3T-GNN의 학습
T-GNN의 오프라인 학습은 일반적으로 시간순(chronological order)으로 수행된다. 대규모 동적 그래프에서의 데이터 배치, 전처리, 주요 학습 단계를 차례로 살핀다.
데이터 배치 (Data Layout)
선행 연구들[26–30, 32]은 입력 데이터 저장과 학습 계산을 모두 GPU에 두는 all-on-GPU 방식을 흔히 사용했으나, 대규모 동적 그래프에서는 이 전략이 성립하지 않는다. 예컨대 약 10억 건의 상호작용을 담은 실세계 동적 지식 그래프 GDELT[33]는 입력 데이터 저장에만 130 GB 이상이 필요해, 통상 11~40 GB인 GPU 메모리 용량을 크게 초과한다. 이에 TGL[34]은 훨씬 큰 CPU 주메모리(흔히 256 GB 초과)를 학습 중 입력 데이터 저장에 활용하는 하이브리드 CPU–GPU 데이터 배치(Fig 2.3)를 제안한다. 학습 시작 직전에 모든 입력 데이터를 보조 저장장치에서 CPU 메모리로 일괄 적재하고, 학습 내내 동적 그래프 데이터·노드 상태 벡터·노드 특징·간선 특징을 CPU 메모리에 유지한다. 이는 대규모 정적 GNN 학습 시스템들[13, 35, 36]의 주류 설계와도 궤를 같이하며, GPU는 모델 계산 전담으로 운용된다.
⟨Fig 2.3⟩ T-GNN 학습을 위한 하이브리드 CPU–GPU 데이터 관리 전략 개요. 전체 그래프 토폴로지·특징 행렬·노드 메모리 상태는 CPU RAM에 상주하고, ①샘플링 → ②수집 → ③전송 → ④계산 → ⑤상태 갱신 → ⑥동기화의 워크플로가 반복된다.
전처리 (Preprocessing)
학습 전에 동적 그래프는 시간 순서 제약(temporal ordering constraint)을 준수하는 다수의 배치로 분할된다(Fig 2.4). 이 제약은 타임스탬프 순서가 결코 위배되지 않도록 하여 그래프 고유의 시간적 성질을 보존한다. 예컨대 배치 1의 상호작용 (v2, v3, e23(t2), t2)를 배치 2의 (v3, v5, e35(t3), t3)와 맞바꾸는 것은 금지된다. T-GNN은 배치를 순차 처리하므로, 미래 정보의 사용을 차단하는 것이 예측 결과의 공정성을 보장한다.
주요 학습 단계 (Main Training Stages)
각 학습 배치는 시간적 이웃 샘플링 → 데이터 회수 → 모델 계산의 세 단계로 진행된다. 대상 노드별 샘플링은 Eq 2.10과 같이 수행하되, 정적 그래프와 달리 더 이른 타임스탬프의 이웃만 고려하여 미래 정보 누출(future information leakage)을 방지한다. 효율 개선을 위해 TGL[34]은 노드들에 대한 동시 샘플링을 지원하는 병렬 샘플러를 제안한다. 샘플링된 서브그래프에 기반해 해당 노드 상태·노드 특징·간선 특징을 회수하여 T-GNN 모델에 입력한다. 계산 가속 측면에서 Orca[37]는 역사적(historical) 임베딩으로 집계 빈도를 줄이고, Zebra[38]는 가장 영향력 있는 시간적 이웃에만 집중하도록 집계 규칙을 수정한다[31].
GNN 학습 하드웨어 시나리오
GNN TRAINING HARDWARE SCENARIOS
단일 GPU 학습
풀배치 학습(Fig 2.5)은 소·중규모 그래프에서만 대체로 가능하며, 그 이상에서는 지수적 이웃 증가가 메모리·실행시간 병목을 일으킨다. 따라서 이웃 샘플링을 결합한 미니배치 학습(Fig 2.6)이 일반적이다 — 대상 노드 집합에서 다중 홉 이웃을 재귀 샘플링해 계산 서브트리를 구성하고, 그 위에서 메시지 패싱과 그래디언트 갱신을 수행한 뒤 다음 배치로 반복한다.
메모리 제약이 최대 관심사다. 통용되는 해법은 학습 그래프를 CPU 메모리에 사전 적재하고 비동기 파이프라인으로 서브그래프 구조와 노드 특징을 GPU에 적재해 순전파·역전파를 수행하는 것이다. PyTorch Geometric과 DGL이 이런 샘플링 기반 미니배치 학습을 지원하며, 레이어 단위 캐싱이나 특징 청킹(feature chunking)으로 중복 읽기와 데이터 전송을 추가로 줄일 수 있다. 다만 샘플링에 의한 분산(variance)과 모델 표현력 사이의 트레이드오프가 발생한다.
다중 GPU 환경 학습
병렬성으로 학습 용량을 한층 확장한다. 두 전략 — 레이어·파라미터 부분집합을 GPU들에 분산하는 모델 병렬화와 모델을 복제하고 입력 데이터를 분산하는 데이터 병렬화 — 중, GNN의 복잡한 계산 그래프 특성상 데이터 병렬화가 더 일반적이다(Fig 2.7–2.8).
주된 과제는 GPU 간 통신과 워크로드 균형이다. 통신은 고속 인터커넥트(NVLink, PCIe P2P)나 NCCL 기반 AllReduce 동기화, 또는 그래디언트 갱신을 조율하는 파라미터 서버로 처리한다. 워크로드 균형은 GPU 간 이웃 접근을 최소화하며 서브그래프를 분배하는 효과적 그래프 파티셔닝에 달려 있다[39–41]. GPU 추가는 처리량을 높이지만 통신 오버헤드와 중복 데이터 저장(예: 크로스 디바이스 캐싱) 같은 새 과제를 낳는다. 각 GPU가 독립적으로 이웃 샘플링을 수행하거나 서로 다른 서브그래프를 처리할 수 있어 샘플링 전략의 유연성은 더 커진다.
GPU 클러스터 분산 학습
노드 간 통신, 동기화, 분산 알고리즘 설계라는 추가 과제가 등장한다. 분산 프레임워크는 배치마다 AllReduce 기반 파라미터 동기화를 수행하는 동기(synchronous) 학습(엄격한 일관성, 통신 오버헤드 부담) 또는 파라미터 서버 기반 그래디언트 갱신의 비동기(asynchronous) 학습(지연 내성 우수, 충돌 해소·수렴 관리 필요)을 채택한다.
크로스 노드 통신이 최대 병목이다. 전통 DNN의 조밀 텐서와 달리 GNN은 희소한 그래프 구조와 특징을 노드 간에 전송해야 한다 — 이웃이 여러 머신에 걸치면 특징 벡터를 네트워크로 가져와야 해 수많은 희소 요청이 발생한다. 일부 시스템은 배치 사전 적재와 서버 내 고속 링크 상의 요청 융합(fusing)으로 이를 완화한다. PS 구조에서는 서버가 노드 임베딩·전역 파라미터를 보관하고 워커가 그래디언트를 push/pull하며, AllReduce 구조는 MPI/NCCL 라이브러리(예: Horovod)로 주기적 동기화를 수행한다. DistDGL[42]은 초기에 CPU 기반 PS 설계로 임베딩의 분산 저장·갱신을 지원했고, GNNLab[43]류의 시스템은 일관된 다중 GPU 학습을 위해 AllReduce를 선호한다.
그래프 파티셔닝·재분배도 핵심이다. 그래프를 서브그래프들로 나눠 노드들에 배정하고 경계(border) 정보를 주기적으로 교환하는 것이 전형이며, 정점·간선 컷 알고리즘(METIS, ParMETIS)과 스트리밍 파티셔닝이 고전적 방법이다. 파티셔닝은 통신을 줄이고 부하를 균형화하지만 경계 노드 동기화 문제를 낳는다. 일부 시스템은 파티션 경계 너머 이웃의 특징을 캐싱해 접근을 가속하고 그래프 갱신 시 일관성 프로토콜을 적용한다. 동적 그래프에 대해 학습 중 파티션·캐싱 정책을 적응적으로 갱신하는 최근 시스템도 있으나, 현행 시스템 대부분은 정적 그래프 구조를 가정한다. 이 밖에 여러 노드가 이웃·서브그래프를 병렬 독립 샘플링한 뒤 로컬 계산을 진행하는 분산 샘플링도 효율 개선의 한 방향이다.
참고문헌
CHAPTER 2 · 43 REFERENCES
- [1] Kipf & Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks (GCN). ICLR.
- [2] Velickovic et al. 2018. Graph Attention Networks (GAT). ICLR.
- [3] Kipf & Welling. 2017. Semi-Supervised Classification with GCNs. ICLR.
- [4] Abadal et al. 2022. Computing GNNs: A Survey from Algorithms to Accelerators. ACM Comput. Surv. 54(9).
- [5] Wu et al. 2021. A Comprehensive Survey on Graph Neural Networks. IEEE TNNLS 32(1).
- [6] Zhou et al. 2023. Narrow the Input Mismatch in Deep GNN Distillation. SIGKDD.
- [7] Zhou et al. 2025. Faster Convergence in Mini-batch GNN Training with Pseudo Full Neighborhood Compensation. PVLDB 18(11).
- [8] Hamilton et al. 2017. Inductive Representation Learning on Large Graphs (GraphSAGE). NIPS.
- [9] Ying et al. 2018. Graph convolutional neural networks for web-scale recommender systems (PinSage). KDD.
- [10] Fey & Lenssen. 2019. Fast graph representation learning with PyTorch Geometric. ICLR Workshop. (원문 [10]은 FastGCN 논의에 인용)
- [11] Zou et al. 2019. Layer-dependent importance sampling for training deep and large GCNs (LADIES). NeurIPS.
- [12] Zeng et al. 2020. GraphSAINT: Graph sampling based inductive learning method. ICLR.
- [13] Yang et al. 2022. GNNLab: A factored system for sample-based GNN training over GPUs. EuroSys.
- [14] Chiang et al. 2019. Cluster-GCN: An efficient algorithm for training deep and large GCNs. KDD.
- [15] Sen et al. 2008. Collective Classification in Network Data (Cora/Citeseer/PubMed). AI Mag. 29(3).
- [16] Leskovec & McAuley. 2012. Social circles: Facebook. SNAP.
- [17] Szklarczyk et al. 2021. The STRING database in 2021 (PPI). Nucleic Acids Res. 49(D1).
- [18] Zafarani & Liu. 2009. BlogCatalog. ASU Social Computing Data Repository.
- [19] Panzarasa et al. 2009. UCI Online Social Network Dataset. UCI ML Repository.
- [20] Debnath et al. 1991. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds (MUTAG). J. Med. Chem. 34(2).
- [21] Borgwardt et al. 2005. Protein function prediction via graph kernels (PROTEINS). ISMB.
- [22] Wale et al. 2008. Comparison of descriptor spaces for chemical compound retrieval and classification (NCI1). Knowl. Inf. Syst. 14(3).
- [23] Yang et al. 2016. Revisiting semi-supervised learning with graph embeddings (IMDB-BINARY 관련). ICML.
- [24] Fey & Lenssen. 2019. Fast graph representation learning with PyTorch Geometric. ICLR Workshop.
- [25] Wang et al. 2019. Deep Graph Library: A graph-centric, highly-performant package for GNNs. arXiv:1909.01315.
- [26] Xu et al. 2020. Inductive representation learning on temporal graphs (TGAT). ICLR.
- [27] Rossi et al. 2020. Temporal Graph Networks for Deep Learning on Dynamic Graphs (TGN). ICML GRL Workshop.
- [28] Wang et al. 2021. Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks (CAW). ICLR.
- [29] Wang et al. 2021. APAN: Asynchronous propagation attention network for real-time temporal graph embedding. SIGMOD.
- [30] Kumar et al. 2019. Predicting dynamic embedding trajectory in temporal interaction networks (JODIE). SIGKDD.
- [31] Rossi et al. 2020. Temporal Graph Networks (TGN). ICML GRL Workshop.
- [32] Li et al. 2023. Zebra: When Temporal GNNs Meet Temporal Personalized PageRank. VLDB 16(6).
- [33] Leetaru & Schrodt. 2013. GDELT: Global data on events, location, and tone, 1979–2012. ISA Annual Convention.
- [34] Zhou et al. 2022. TGL: A General Framework for Temporal GNN Training on Billion-Scale Graphs. PVLDB.
- [35] Zhang et al. 2023. DUCATI: A Dual-Cache Training System for GNNs on Giant Graphs with the GPU. PACMMOD 1(2).
- [36] Lin et al. 2020. PaGraph: Scaling GNN training on large graphs via computation-aware caching. SoCC.
- [37] Li et al. 2023. Orca: Scalable Temporal GNN Training with Theoretical Guarantees. PACMMOD 1(1).
- [38] Li et al. 2023. Zebra: When Temporal GNNs Meet Temporal Personalized PageRank. PVLDB 16(6).
- [39] Lin et al. 2020. PaGraph: Scaling GNN Training on Large Graphs via Computation-Aware Caching. SoCC.
- [40] Zhu et al. 2019. AliGraph: A Comprehensive Graph Neural Network Platform. PVLDB 12(12).
- [41] Ma et al. 2019. NeuGraph: Parallel Deep Neural Network Computation on Large Graphs. ATC.
- [42] Zheng et al. 2022. Distributed Hybrid CPU and GPU Training for GNNs on Billion-Scale Heterogeneous Graphs (DistDGL). SIGKDD.
- [43] Yang et al. 2022. GNNLab: A Factored System for Sample-Based GNN Training over GPUs. EuroSys.