배경
BACKGROUND
그래프 신경망(GNN)은 대규모 그래프로부터 복잡한 구조 정보와 의미 정보를 추출하는 강력한 도구로 부상했으며, 소셜 네트워크 분석[15], 금융 리스크 평가[2], 지식 그래프 구축[34], 추천 시스템[10] 등 광범위한 그래프 기반 응용에서 지속적인 인기를 얻고 있다.
모델 아키텍처는 다양하지만 대부분의 GNN은 그래프 구조를 따라 노드 간 정보를 교환하는 메시지 패싱(message passing) 방식을 채택한다. 이 방식은 재귀적인 이웃 정보 집계를 수반하며, 바로 이 지점이 대규모 그래프 데이터셋에서 GNN을 학습할 때 심각한 병목을 만든다. 구체적으로 세 가지 도전과제가 존재한다.
머신 간 높은 통신 비용
풀배치(full-batch) 학습에서 파티션 간 이웃 집계를 위한 통신이 폭증한다. Sancus[27]의 측정에 따르면 8-GPU 머신에서 GCN을 Ogbn-Products에 학습할 때 통신 시간이 전체의 90%를 초과한다.
CPU–GPU 간 과도한 데이터 이동
미니배치(mini-batch) 학습에서는 데이터 이동이 엔드투엔드 학습 시간을 지배한다. Ogbn-Papers100M[14]과 같이 그래프가 커질수록 문제는 더 심각해진다.
낮은 하드웨어 활용률
모델 학습 중 계산 자원이 충분히 활용되지 못한다. 최근 연구[1]는 자원 활용률 개선만으로 에폭당 학습 효율을 약 10배 높일 수 있음을 보였다.
그래프 데이터의 규모가 계속 커짐에 따라 효율적인 GNN 학습 시스템의 개발은 갈수록 중요해지고 있다. 현행 학습 시스템은 하이브리드 CPU–GPU 플랫폼 위에서 그래프 데이터를 처리하며, 순전파·역전파의 복잡한 계산 논리를 따르면서 이기종 하드웨어 간 데이터 이동을 조율한다. 복잡한 그래프 처리를 위한 효율적 기법을 오랫동안 연구해 온 데이터베이스 연구자들은 최근 GNN 학습 가속을 위한 데이터 관리 기법 탐구에 힘을 쏟고 있다. 이 연구 흐름은 GNN 모델 개발과 병행하여 진행되되, 모델 성능을 훼손하지 않으면서 학습 효율을 높이는 것에 초점을 둔다.
이 장은 대규모 그래프에서의 GNN 학습 가속을 위한 최근 노력을 개관한다. 그래프 데이터 생애주기에 기반해 학습 과정을 그래프 전처리, 배치 생성, 데이터 전송, 모델 학습의 4대 단계(Fig 1.1)로 바라보고, 각 단계에서 학습 효율을 개선하는 혁신적 데이터 관리 아이디어를 논의한다. 중앙집중식과 분산 학습 환경을 모두 고려하며, 정적 그래프와 동적 그래프 및 각각의 GNN 모델이 갖는 뚜렷한 특성 차이로 인해, 먼저 대규모 정적 그래프에서의 효율적 학습을 다룬 뒤 대규모 동적 그래프에서의 학습 노력을 살핀다.
그래프 전처리
GRAPH PREPROCESSING
기존 연구들은 GNN 학습 효율을 높이기 위해 필수적인 그래프 전처리를 수행할 것을 제안한다. 이 절은 그래프 크기 축소, 그래프 파티셔닝, 그래프 재정렬이라는 세 가지 대표 전처리 기법과, 이들이 이후 배치 생성 및 전송 효율에 미치는 영향을 소개한다.
대규모 그래프 학습은 시간이 많이 걸리므로, 모델 정확도를 유지하면서 학습 그래프 자체를 압축하는 것이 직관적 해법이다. 세 가지 기법이 통용된다. 그래프 조대화(coarsening)[24]는 원본 그래프의 노드들을 슈퍼노드로 묶어 크기를 줄이고, 그래프 희소화(sparsification)[19]는 중복되거나 유의미하지 않은 관계를 나타내는 간선을 제거한다.
그래프 응축(condensation)은 앞의 두 기법과 달리 더 작은 합성(synthetic) 그래프를 새로 구성한다. 응축 문제는 흔히 이중 최적화(bi-level optimization)로 정식화된다 — 내부 루프에서 합성 데이터로 신경망을 학습하고, 외부 루프에서 그 결과를 기반으로 합성 데이터를 갱신한다. 이 문제는 계산적으로 매우 비싸거나 다루기 어려울 수 있어, 기존 연구들은 (1) 내부 루프의 가속[6], 또는 (2) 내부 루프의 모델 학습을 닫힌 해(closed-form solution)로 대체하여 이중 최적화 자체를 회피[30]하는 방향으로 효율을 개선한다. 일반화 능력 향상을 위한 graph-free 응축[35] 연구도 존재한다.
디바이스 메모리의 한계 때문에, 분산 GNN 학습에서는 그래프 구조와 특징(feature) 데이터를 파티셔닝하여 더 작은 서브그래프들을 만든다. 현행 파티셔닝 알고리즘은 통신 비용 절감과 서브그래프 간 워크로드 균형을 목표로 한다. 그래프 구조 분할에는 METIS·랜덤 파티셔닝 같은 전통 알고리즘[4, 27]이나 GNN 학습에 특화된 전략[17, 26]을 사용할 수 있다. 특징 데이터에 대해서는 P³[9]가 수직 파티셔닝(vertical partitioning)으로 통신 비용을 최적화한다.
그래프의 정점을 재정렬하는 것은 지역성(locality)을 높이는 효과적 방법으로, 모델 계산과 데이터 전송 양쪽에 이롭다. GNNAdvisor[29]는 그래프 합성곱 커널의 계산 지역성 개선을 위해 그래프를 선택적으로 재정렬하고, DUCATI[33]는 접근 빈도 기반 재정렬로 토폴로지 데이터에 대한 경량 캐시 구축·조회를 용이하게 한다. 통합 메모리(unified memory)로 그래프 토폴로지를 순회할 때는 HALO 재정렬[13]이 PCIe 대역폭 활용률을 높여 배치 데이터 전송을 가속한다.
배치 생성
BATCH GENERATION
GNN 학습에서 그래프 샘플링은 배치를 생성하는 강력한 기법으로 자리 잡았다. 원본 그래프로부터 노드와 그에 연결된 간선을 선택하고, 샘플링된 서브그래프가 다운스트림 GNN 학습에 입력되는 배치 역할을 한다.
GNN 학습 워크플로의 특성에 맞춘 다양한 샘플링 접근이 개발되었다. 노드 단위(node-wise) 샘플링은 이웃의 부분집합에서만 메시지를 집계하여 GNN의 지수적으로 증가하는 의존성에서 오는 계산 부담을 완화한다. 레이어 단위(layer-wise) 샘플링은 각 네트워크 레이어마다 독립적으로 샘플링하고 중요도 샘플링(importance sampling)을 활용해 샘플 크기를 상수로 유지함으로써 계산량 증가를 효과적으로 통제한다. 서브그래프 단위(subgraph-wise) 샘플링은 하나의 서브그래프를 생성해 모든 레이어의 계산에 재사용한다.
나아가 일부 연구는 특징 저장·추출에서의 공간 지역성을 정교하게 고려하면 전송 비용을 크게 줄일 수 있음을 보였다. 특징 지향(feature-oriented) 샘플링[32]은 노드 특징의 선택으로 샘플링을 시작하고, 이를 바탕으로 미니배치에 대응하는 서브그래프를 구성한다.
효율적 샘플링의 핵심은 시스템 내 가용 하드웨어의 계산 능력을 활용하는 것이다. 뛰어난 병렬 계산 능력을 갖춘 GPU가 이상적인 선택지이며, GPU에서 직접 서브그래프를 생성하면 샘플을 디바이스 메모리로 옮기는 추가 비용도 사라진다. NextDoor[16]는 단일 GPU에서 그래프 샘플링을 수행한 선구적 연구로, 전체 그래프를 디바이스 메모리에 적재하고 동일한 경유(transit) 노드를 묶어 처리하는 transit-parallelism 전략으로 샘플링을 가속한다.
호스트 메모리의 큰 용량을 활용해 확장성을 높이기 위해 UVA(Unified Virtual Addressing) 기법이 그래프 샘플링에 도입되었다[4, 33]. 그래프 구조를 호스트 메모리에 두고 샘플링은 GPU에서 실행하여, 호스트와 디바이스의 결합된 자원을 함께 활용한다.
데이터 전송
DATA TRANSFER
CPU와 GPU 사이, 또는 다중 GPU 사이의 효율적 데이터 전송은 대규모 그래프에서 GNN 학습 효율을 담보하는 데 필수적이다. 모델 계산에 필요한 데이터가 로컬에 존재하지 않을 수 있기 때문이다. 무엇을 전송해야 하는지는 적용된 학습 방식 — 미니배치 기반인지 풀배치 기반인지 — 에 따라 달라진다.
입력 그래프 데이터 전송
미니배치 학습에서는 입력 그래프 데이터(초기 노드 특징 벡터와 그래프 구조 정보)의 크로스 디바이스 전송이 불가피하며, 이 과정이 상당한 비용을 유발한다. 일반적 해법은 로컬 캐시로 전송량을 줄이고 정교한 캐시 관리 정책을 쓰는 것이다. PaGraph[26]와 GNNLab[31]은 노드 특징의 지역성을 활용해 특정 hotness 지표에 따라 학습 전에 특징 벡터를 로컬에 캐싱한다. DUCATI[33]는 여기서 나아가 그래프 구조 데이터의 지역성까지 활용해 별도의 구조 데이터 GPU 캐시를 추가하고, 정제된 할당기(allocator)로 두 종류의 캐시를 함께 관리하여 CPU–GPU 간 두 입력 데이터의 총 전송량을 최소화한다.
중간 노드 임베딩 전송
풀배치 학습에서는 대규모 그래프가 통상 디바이스들에 분할 배치된다. 이때 대상 노드의 전체 이웃(full-neighbor) 집계를 위해, 각 GNN 레이어에서 이웃이 집계된 노드 표현인 중간 노드 임베딩을 디바이스 간에 전송해야 한다. DGCL[3]은 시스템 토폴로지를 고려하여 각 노드의 중간 임베딩에 대한 최적 전송 경로를 찾아 비용을 최소화한다. NeutronStar[28]는 로컬에서의 중복적인 상향식(bottom-up) 이웃 집계를 감수하는 대신 임베딩 전송 비용을 절감한다. Sancus[27]는 특정 학습 에폭에서 GPU 간 중간 임베딩 전송을 유연하게 생략하는 skip-broadcast 메커니즘을 제안하며, 이는 임베딩 신선도(staleness)에 대한 정제된 관리 규칙들에 의해 제어된다.
모델 학습
MODEL TRAINING
순전파와 역전파, 즉 모델 학습 자체의 효율 역시 전체 학습 효율에 중요하다. 연구자들은 중복 계산의 제거[18]와 계산 스케줄의 최적화를 탐구해 왔다. 후자에는 CPU–GPU 협업 계산 환경에서 자원 활용률을 높이기 위한 연산별 자원 할당 최적화[25], 학습 병렬성 최적화[25], 그리고 하드웨어 위에서 계산 그래프와 연산자(operator)의 효율을 개선하는 접근[7, 8]이 포함된다.
동적 그래프에서의 학습
TRAINING ON DYNAMIC GRAPHS
전통적인 정적 그래프와 달리, 현실 세계의 많은 그래프는 상호작용 패턴이 진화하는 동적 특성을 보인다. 동적 그래프는 통상 두 유형으로 나뉜다 — 이산 시간 동적 그래프(DTDG)와 연속 시간 동적 그래프(CTDG)이며, 각각 동적 GNN(D-GNN)과 시간적 GNN(T-GNN)이 처리를 담당한다. 그래프의 동적 성질은 학습 중 데이터 전송과 계산의 가속에 새로운 도전과제와 최적화 기회를 함께 가져온다.
D-GNN 학습: Chakaravarthy et al.[5]은 서로 다른 그래프 스냅숏 간의 위상적 유사성에 착안하여, 스냅숏 전송 비용을 줄이는 그래프 차분(graph-difference) 기반 전송 기법을 설계한다.
T-GNN 학습: ETC[11]는 중복적인 데이터 접근 패턴을 식별하고 중복 인지(redundancy-aware) 데이터 접근 정책으로 입력 특징의 전송량을 줄인다. SIMPLE[12]은 CTDG에서 시간 정보와 빈도(frequency) 정보 사이의 복잡한 얽힘(entanglement) 효과를 포착하고, GPU 상의 동적 데이터 배치(dynamic data placement)로 전송 비용을 절감한다.
D-GNN 학습: Li et al.[21]은 그래프 스냅숏 간에 재사용 가능한 중간 임베딩을 식별하고, 다음 스냅숏에서 절약되는 계산 시간을 최대화하는 캐시 정책을 제안한다.
T-GNN 학습: Orca[22] 역시 중간 임베딩을 캐싱하되, 주어진 GPU 캐시 예산 아래에서 전체 재계산 비용을 최적으로 최소화하는 재사용 거리(reuse-distance) 기반 캐시 정책을 채택한다. Zebra[23]는 T-GNN 학습에서 노드 영향력의 시간적 효과에 주목하여, 가장 영향력 있는 이웃들에 대해서만 단일 레이어 집계를 수행함으로써 계산 효율을 높인다.
이 책의 구성
OUTLINE OF THIS BOOK
이 책의 나머지 부분은 다음과 같이 구성된다.
GNN의 기초 개념과 학습 기법을 소개한다. 정적·동적 그래프 설정과 함께 단일 GPU, 다중 GPU, 분산 클러스터 등 다양한 학습 하드웨어 시나리오를 다룬다.
효율적·확장적 GNN 학습을 저해하는 두 가지 데이터 전송 문제를 규명하고, 이를 해결하는 확장 가능한 그래프 샘플링 알고리즘과 효율적인 GNN 학습 시스템을 제안한다.
계산 가속 기법에 초점을 맞추어, 모델 실행 계획(execution planning) 측면과 희소 연산자(sparse operator) 최적화 측면에서 각각 하나씩 두 가지 해법을 제안한다.
분산 GNN 학습 문제를 연구하고, 신선도 인지(staleness-aware)·통신 회피(communication-avoiding) 탈중앙 GNN 시스템을 제안한다.
시간적 GNN 학습 영역을 탐구하며, 부적합한 배칭과 대규모 그래프에서의 높은 입력 데이터 적재 비용이라는 병목을 해소하는 상호 보완적인 두 시스템 프로토타입을 다룬다.
※ 위 항목은 각각 이 책의 제2장~제6장에 해당한다.
참고문헌
CHAPTER 1 · 35 REFERENCES
- [1] Ai et al. 2024. NeutronOrch: Rethinking Sample-based GNN Training under CPU-GPU Heterogeneous Environments. VLDB 17(8).
- [2] Bi et al. 2022. Company-as-tribe: Company financial risk assessment on tribe-style graph with hierarchical GNNs. KDD.
- [3] Cai et al. 2021. DGCL: An efficient communication library for distributed GNN training. EuroSys.
- [4] Cai et al. 2023. DSP: Efficient GNN training with multiple GPUs. PPoPP.
- [5] Chakaravarthy et al. 2021. Efficient scaling of dynamic graph neural networks. SC.
- [6] Fang et al. 2024. EXGC: Bridging Efficiency and Explainability in Graph Condensation. WWW.
- [7] Fang et al. 2020. Optimizing DNN computation graph using graph substitutions. VLDB 13(12).
- [8] Fang et al. 2024. STile: Searching Hybrid Sparse Formats for Sparse Deep Learning Operators Automatically. PACMMOD 2(1).
- [9] Gandhi & Iyer. 2021. P3: Distributed deep graph learning at scale. OSDI.
- [10] Gao et al. 2022. Graph neural networks for recommender system. WSDM.
- [11] Gao et al. 2024. ETC: Efficient Training of Temporal GNNs over Large-scale Dynamic Graphs. VLDB 17(5).
- [12] Gao et al. 2024. SIMPLE: Efficient Temporal GNN Training at Scale with Dynamic Data Placement. PACMMOD 2(3).
- [13] Gera et al. 2020. Traversing large graphs on GPUs with unified memory (HALO). VLDB 13(7).
- [14] Hu et al. 2020. Open Graph Benchmark: Datasets for machine learning on graphs. NeurIPS 33.
- [15] Jain et al. 2023. Opinion leaders for information diffusion using GNN in online social networks. TWEB 17(2).
- [16] Jangda et al. 2021. Accelerating graph sampling for graph ML using GPUs (NextDoor). EuroSys.
- [17] Jia et al. 2020. Improving the accuracy, scalability, and performance of GNNs with ROC. MLSys 2.
- [18] Jia et al. 2020. Redundancy-free computation for graph neural networks. KDD.
- [19] Jiang et al. 2021. Pre-training on large-scale heterogeneous graph. KDD.
- [20] Kipf & Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks (GCN). ICLR.
- [21] Li & Chen. 2021. Cache-based GNN system for dynamic graphs. CIKM.
- [22] Li et al. 2023. Orca: Scalable Temporal GNN Training with Theoretical Guarantees. PACMMOD 1(1).
- [23] Li et al. 2023. Zebra: When Temporal GNNs Meet Temporal Personalized PageRank. VLDB 16(6).
- [24] Li et al. 2022. CC-GNN: A community and contraction-based graph neural network. ICDM.
- [25] Li et al. 2024. DAHA: Accelerating GNN Training with Data and Hardware Aware Execution Planning. VLDB 17(6).
- [26] Lin et al. 2020. PaGraph: Scaling GNN training on large graphs via computation-aware caching. SoCC.
- [27] Peng et al. 2022. SANCUS: Staleness-Aware Communication-Avoiding Full-Graph Decentralized Training in Large-Scale GNNs. VLDB 15(9).
- [28] Wang et al. 2022. NeutronStar: Distributed GNN Training with Hybrid Dependency Management. SIGMOD.
- [29] Wang et al. 2021. GNNAdvisor: An adaptive and efficient runtime system for GNN acceleration on GPUs. OSDI.
- [30] Xu et al. 2023. Kernel Ridge Regression-Based Graph Dataset Distillation. KDD.
- [31] Yang et al. 2022. GNNLab: A factored system for sample-based GNN training over GPUs. EuroSys.
- [32] Zhang et al. 2022. Feature-Oriented Sampling for Fast and Scalable GNN Training. ICDM.
- [33] Zhang et al. 2023. DUCATI: A Dual-Cache Training System for GNNs on Giant Graphs with the GPU. PACMMOD 1(2).
- [34] Zhang et al. 2019. NSCaching: Simple and efficient negative sampling for knowledge graph embedding. ICDE.
- [35] Zheng et al. 2024. Structure-free graph condensation: From large-scale graphs to condensed graph-free data. NeurIPS 36.