Ginex++: Acceleration Techniques for Training Billion-scale Graph Neural Networks on a Single Machine

Abstract

Recently, lots of efforts have been made to seek meaningful inspirations from graph structured datasets using Graph Neural Networks (GNNs). The size of real-world graph datasets grows over time, and there appear cases where the dataset is too big to fit in a single machine's main memory. Lately, several approaches have been made to leverage high-performance storage devices such as NVMe SSDs to scale-up a single machine for GNN training. As opposed to distributed training systems, which scale-out multiple machines for GNN training, disk-based GNN training systems promise equivalent training quality in a more cost-effective manner with an endurable training time increase. Ginex [35] is the state-of-the-art SSD-based GNN training system targeted on billion-scale graph datasets on a single machine. Ginex restructures the conventional GNN training pipeline by separating sample and gather steps, and thereby realizes a provably optimal cache policy known as Belady's algorithm. Although it does a decent job by minimizing the latency arose from gather, the newly introduced overhead called inspect becomes non-negligible. We apply two acceleration techniques directly purposed to decrease inspect overhead on top of Ginex, and name it Ginex++. Two techniques are called neighbor cache compression and k-hop approximation for changeset precomputation. By evaluating these techniques on four billion-scale graph datasets, Ginex++ achieves 1.28x higher training throughput on average (1.51x at maximum) than Ginex.

최근 그래프 신경망(GNN)을 사용하여 그래프로 구조화된 데이터에서 의미 있는 영감을 찾으려는 많은 노력이 이루어지고있다. 현실의 그래프 데이터는 시간이 지남에 따라 그 크기가 커지고, 이에 따라 단일 머신의 메모리에 맞지 않는 경우를 쉽게 찾을 수 있다. 이에 따라 최근 NVMe SSD와 같은 고성능 저장 장치를 활용하여, GNN 학습을 위해 단일 머신을 확장하는 여러 접근 방식이 제안되었다. GNN 학습을 위해 여러 머신을 동시에 사용하는 분산 시스템과 달리, 단일 머신에서 디스크를 기반으로 한 GNN 학습은 약간의 학습 시간 증가가 있긴 하지만 동등한 학습 품질을 보장하면서도 비용 측면에서 더욱 효율적인 대안을 제공한다. 그 중 하나인 Ginex[35]는 단일 머신에서 수십 억 규모의 그래프 데이터를 대상으로 GNN을 학습시키는 SSD 기반의 최첨단 학습 시스템이다. Ginex는 sample 단계와 gather 단계를 분리하는 방식으로 기존 GNN 학습 파이프라인을 재구성함으로써 Belady's algorithm으로 알려진 최적의 캐시 정책을 실현한다. 이렇게 Ginex는 gather 단계에서 걸리는 시간을 최소화하하는데 성공하였지만, 이 때문에 새로 도입된 inspect라는 오버헤드는 무시할 수 없게 되었다. 이에 본 논문에서는 inspect 오버헤드를 줄이기 위한 두 가지 가속화 기법을 Ginex에 적용하고 이를 Ginex++라고 명명한다. 두 기법은 이웃 캐시 압축과 changeset의 사전 계산을 위한 k-hop 근사이다. 네 개의 수십 억 규모의 그래프 데이터에 이러한 기법을 적용하여 평가한 결과, Ginex++은 Ginex보다 평균적으로 1.28x (최대 1.51x) 더 높은 학습 처리량을 달성한다.