제5장 · 분산 GNN 학습 — Graph Neural Network Training

5.1

배경

BACKGROUND

GNN[1]의 성공은 실세계 그래프 모델링의 최신 진보를 이끌었다. 높은 수준에서 GNN은 아키텍처가 입력 그래프의 하부 위상과 자연스럽게 정렬되는 구조 인지 모델로, 대상 노드 이웃의 정보를 반복 집계함으로써 구조적 의존성과 노드 특징을 함께 포착한다. 그러나 유한한 시간 예산 안에서 모든 데이터를 처리하기 어렵고 기존 알고리즘의 확장성이 제한적이어서, 대규모 그래프로의 확장은 여전히 난제다. 끊임없이 커지는 데이터·모델 규모 아래 메모리 요구를 완화하려면 분산 GNN 처리가 불가피한 선택이 된다. 선행 연구는 샘플링 기반 분산 GNN 학습을 탐구했으나 대개 정보 손실[2–4], 추가 샘플링 오버헤드[3], 심지어 수렴 보장의 결여[5]라는 대가를 치른다. 이에 이 장은 풀-GNN(full-GNN)의 분산 학습에 초점을 둔다.

전통적 그래프 처리나 기계학습과 비교해 분산 풀-GNN은 새로운 시스템 수준 도전을 제기한다. 상당한 메모리 풋프린트를 넘어, 불규칙한 이웃 접근이 반복적 학습 절차와 긴밀히 결합되어 있어 메모리 집약적이면서 동시에 계산 집약적이다[6, 7]. 그 결과 무거운 통신이 효율의 핵심 장애물이 된다 — 그래디언트와 파라미터에 더해 워커들이 중간 임베딩을 빈번히 교환해야 한다. 학습은 대상 노드, 그 이웃, 다중 홉 이웃을 지속적으로 질의하므로 과정 전반에서 임베딩과 그래디언트가 워커 사이를 오가야 하며, 실무에서 이 오버헤드는 전체 학습 시간의 80% 이상을 차지할 수 있다[2, 4, 8].

CENTRALIZED · FIG 5.2a

파라미터 서버(PS) 패러다임

대부분의 기존 분산 GNN 시스템[3, 8–12]이 따르는 중앙집중 방식이다. 효율과 확장성을 위해 흔히 무거운 전처리와 복잡한 실행 워크플로에 의존한다. 그러나 GNN의 본질적 통신 요구 탓에 모든 워커와 중앙 PS 사이의 빈번한 교환, 그리고 낙오자(straggler)가 유발하는 동기화 지연이 겹쳐 높은 통신 오버헤드로 이어질 수 있다[2].

DECENTRALIZED · FIG 5.2b

워커 간 직접 교환

탈중앙 구조는 대개 더 강건하고 배포가 쉽다 — PS 구현·튜닝의 공학적 부담을 피하고, 중앙집중적 대역폭 병목을 완화하며, 단일 실패점을 제거한다[13]. 대형 신경망에서는 이론적으로도 탈중앙 방식이 더 유리함이 밝혀졌다[14]. Tripathy 등[4]의 CAGNET이 GNN 학습에 특화된 유일한 최신 탈중앙 병렬 알고리즘[15]으로, 각 워커가 모델 파라미터 전체 복제본을 유지해 중앙집중 통신을 줄인다. 그럼에도 임베딩·그래디언트의 중복적이고 불필요한 브로드캐스트를 여전히 감수하며, 워커들이 낙오자를 기다리며 동기화해야 해 오버헤드가 증폭된다.

Sancus의 4가지 착안

⟨Fig 5.1 · 5.3⟩ 정점 중심 분산 GNN의 세밀한 이웃 페칭과, 탈중앙 GNN 계산을 순차 행렬 곱으로 추상화한 Sancus의 블록 브로드캐스트 비교. 각 GPUi−1은 A_i·H_i 로컬 샤드와 W 전체 복제본을 보유한다.

IDEA 1

순차 행렬 곱으로의 추상화

불규칙한 GPU 간 통신을 우회하기 위해 분산 GNN 학습의 병렬 알고리즘[4]을 재검토하고 근본적으로 다른 방식으로 오버헤드를 줄인다. 탈중앙 GNN 계산을 순수하게 행렬 곱 연산의 시퀀스로 취급하면, 각 GPU는 그래프 특유의 의미론에 의존하지 않고 분할된 부분행렬만 적재한다. 정합한 행렬 블록을 이동시켜 데이터 병렬성을 활용함으로써 집약적 이웃 페칭에서 오는 통신을 회피한다.

IDEA 2

역사적 임베딩의 캐싱과 생략

탈중앙 설정에서 통신을 더 줄이기 위해 역사적 임베딩을 캐시하고 브로드캐스트를 건너뛴다. 역사적 임베딩은 각 워커에서 이전 에폭에 계산된 임베딩 부분행렬 — Fig 5.3에서 GPUi−1이 로컬 생성한 H_i — 로 정의한다. 이 관찰에 기반해 캐싱을 활용하고 skip-broadcast 연산자를 새로 설계해 재사용을 가능하게 한다.

IDEA 3 · 4

유계 신선도와 낮은 전처리 부담

GPU 간 혼합 버전 임베딩이 유발하는 시스템 신선도를 통제하기 위해, 중앙집중 설정에서 널리 쓰이는 유계 그래디언트 신선도[16]를 역사적 임베딩으로 일반화한 유계 임베딩 신선도 지표군을 도입한다. 신선도가 규정 한계 내면 skip-broadcast로 통신을 직접 회피하고, 너무 낡으면 최신 결과를 브로드캐스트하고 캐시를 갱신해 시스템 신선도를 유계로 유지한다. 또한 Sancus는 전처리 부담이 거의 없고 임의의 행렬 블로킹과 직접 행렬 연산에 기반한 분산 GNN 학습에 곧바로 적용 가능하다.

DEFINITION 5.1 — 노드 수준 그래프 표현 학습

L-레이어 GNN 모델, 인접행렬 A를 갖는 무향 그래프 𝒢 = (𝒱, ℰ), 초기 특징 행렬 X, 레이블 Y가 주어졌을 때, 표현 행렬 H^(L)은 모든 노드의 학습된 저차원 벡터 표현으로 구성된다. 형식적으로 손실 함수 ℒ과 목표 Y에 대해 다음을 푼다.

min_W ℒ(H^(L), Y) s.t. H^(ℓ) = σ(H^(ℓ−1), Â; W^(ℓ−1)), ∀ℓ ∈ [1, L]PROBLEM

기호	설명	기호	설명
A	그래프의 인접행렬 (N × N)	T^(ℓ)	곱 ÂH^(ℓ)의 중간 결과 행렬
Â	대칭 정규화 후의 인접행렬 (N × N)	∇_Z^(ℓ)ℒ = δ^(ℓ)	ℓ번째 레이어에서 Z^(ℓ)에 대한 손실 ℒ의 그래디언트 행렬
W^(ℓ)	ℓ번째 레이어의 가중치 행렬 (F × F)	∇_W^(ℓ)ℒ	ℓ번째 레이어에서 W^(ℓ)에 대한 손실 ℒ의 그래디언트 행렬
H^(ℓ)	ℓ번째 레이어의 임베딩 행렬 (N × F)	ℒ, η	GNN의 손실, 학습률
Z^(ℓ)	ℓ번째 레이어에서 활성 함수의 입력 행렬 (N × F)	Δ, P(i)	신선도 한계, 분산 GNN의 i번째 프로세스

⟨Table 5.1⟩ 주요 기호와 표기의 요약.

5.2

Sancus 프레임워크

THE SANCUS FRAMEWORK

5.2.1개요 — 다섯 단계

Sancus는 적응적·신선도 인지·통신 회피 탈중앙 GNN 시스템이다. 근본적으로 단순하면서 효과적이다 — 병렬 계산을 위한 일반적 통신 회피 행렬 블로킹 알고리즘 위에서, 낡은 역사적 임베딩을 캐시·재사용하고 그에 따라 브로드캐스트를 건너뛴다. 전체 그래프와 노드 특징이 분할되어 워커 전반의 개별 프로세스에 배정되며, 학습은 다섯 단계로 진행된다.

데이터 적재

전체 그래프의 희소 인접행렬과 조밀 임베딩 행렬을 블록으로 분할해 개별 워커에 적재한다. 각 워커는 전체 모델의 자기 복제본을 유지한다.

신선도 검사

직전 계산 결과를 브로드캐스트하기 전에, 각 GPU에서 역사적 임베딩의 신선도가 제안된 한계 내인지 확인한다.

임베딩 브로드캐스트

한계 내면 브로드캐스트를 건너뛰고 캐시된 역사적 임베딩을 재사용한다. 초과하면 최신 결과를 모든 워커에 브로드캐스트하고 캐시를 갱신한다.

모델 계산

각 GPU가 최신 임베딩 또는 캐시된 낡은 임베딩을 사용해 GNN 계산을 수행한다.

결과 캐싱

갱신된 임베딩이 다음 반복으로 전달되어, 브로드캐스트 이전에 다시 신선도 검사를 받는다.

※ Fig 5.4의 전체 아키텍처에 대응한다. 지표들은 각 워커에서 국소적으로 평가되므로, Sancus는 중앙 컨트롤러나 전역 모니터를 필요로 하지 않고 탈중앙 설계를 보존한다.

5.2.2신선도 인지 통신 회피 탈중앙 학습

Algorithm 1이 완전한 절차를 기술하며, 세 핵심 구성요소에 의존한다 — (1) 워커 i의 상태를 나타내는 워커 상태 플래그 F(i)로 각 워커는 ACTIVE 또는 STALE로 표시되어 Skip-Broadcast를 가능하게 하고, (2) 다른 워커에서 받은 역사적 임베딩을 저장해 이후 반복에서 반복 재사용할 수 있는 캐시, (3) 서로 다른 워커가 서로 다른 반복에서 계산된 임베딩을 소비할 수 있게 하면서 시스템 신선도를 통제하는 유계 임베딩 신선도의 허용이다.

전처리 단계에서 Sancus는 그래프 관련 행렬을 블록으로 분해하는 폭넓은 분할기와 호환된다 — DistDGL[11]·AliGraph[12] 같은 시스템이 채택한 METIS[17]부터 무작위 분할 같은 경량 대안까지 포함한다. 희소 인접행렬 Â와 조밀 임베딩 행렬 H가 워커 프로세스 P(i), i ∈ [1, p]에 블록 분산되며, Â(N × N)는 행·열 양방향으로 p × p 블록으로, H(N × F)는 행 방향으로만 p 블록으로 분할된다. 반면 (F × F) 가중치 행렬 W는 조밀한 상태로 모든 프로세스에 복제된다. 곱 ÂH^(ℓ)에 대해 P(i)의 프로세스별 부분 결과를 T_i^(ℓ) = Σ_j=1^p Â_ijH_j^(ℓ)로 표기한다.

성긴(coarse-grained) 행렬 블록만 탈중앙 워커 사이에 교환된다 — 정점 중심 프레임워크에서 이웃을 가져오기 위해 쓰이던 불규칙·세밀한 요청–전송 메시징 패턴이 제거된다

⟨Fig 5.5⟩ 순차 행렬 곱 관점의 통신 회피 데이터 병렬 GNN 학습. 순전파와 역전파가 표준 집합 통신(링 기반 파이프라인 Broadcast, AllReduce)으로 조율되며 동시 실행된다.

ALGORITHM 1 — 임의 일반 블록 행 분해 기반 탈중앙 STALE 병렬 GNN 학습

Input: G = (V, E); 희소 인접행렬 Â; 조밀 특징 행렬 H⁽⁰⁾; 조밀 가중치 행렬 W
Output: 노드 임베딩 행렬 H⁽ᴸ⁾
        Â와 H는 p × p 프로세스 그리드에 분산되고, 각 프로세스 P(i)는 N/p개의 연속 블록 행을 받는다

1 Preprocessing: 블록 행 분할
2 for all process P(i) in parallel do
3 procedure FORWARD PASS
4   for ℓ = 1, ⋯, L do
5    for j = 1 to p do
6     if F(j) == ACTIVE then  ▷ 워커 상태 플래그
7      BROADCAST(H_j⁽ˡ⁻¹⁾)
8      CACHE(H_j⁽ˡ⁻¹⁾)  ▷ P(j)로부터 받은 최신 H_j 캐싱
9      ▷ 최신 H_j로 중간 결과 계산
10     T_i⁽ˡ⁻¹⁾ ← T_i⁽ˡ⁻¹⁾ + Â_ij H_j⁽ˡ⁻¹⁾
11    else  ▷ Skip-Broadcast
12     ▷ 역사적 H̃_j로 중간 결과 계산
13     T_i⁽ˡ⁻¹⁾ ← T_i⁽ˡ⁻¹⁾ + Â_ij H̃_j⁽ˡ⁻¹⁾
14    end if
15    Z_i⁽ˡ⁾ ← T_i⁽ˡ⁻¹⁾ W⁽ˡ⁻¹⁾  ▷ 활성 함수 입력
16    H_i⁽ˡ⁾ ← σ(Z_i⁽ˡ⁾)  ▷ 임베딩 갱신
17    F(i) ← STALE(H_i⁽ˡ⁾)  ▷ 워커 i의 상태 갱신 — Def 5.2 / 5.3 / 5.4에 따름
18   end for  19 end for
20 procedure BACKWARD PASS
21  for ℓ = L − 1, ⋯, 0 do
22   δ_i⁽ˡ⁾ ← GRADIENT_CLIP(δ_i⁽ˡ⁾)
23   BROADCAST(δ_i⁽ˡ⁾) 후 그래디언트로 W 갱신 (AllReduce)
24  end for  25 end procedure  26 end procedure  27 end for

각 통신 국면 시작 시 프로세스 j는 자신의 중간 임베딩 블록 H_j^(ℓ−1)의 신선도를 평가한 뒤(Line 6) 전파 여부를 결정한다. ACTIVE면 루트 랭크에서 순차적 일대전체 브로드캐스트로 모든 랭크에 전파되고(Line 7) 받은 블록은 캐시에 저장된다(Line 8). STALE이면 Skip-Broadcast가 호출된다 — 프로세스 j는 현재 통신 스케줄의 송신 측에서 제거되지만, 타인의 갱신을 얻기 위해 브로드캐스트 그래프의 수신자로는 남는다. 이 라운드에 j는 H_j^(ℓ−1)를 전송하지 않으므로 다른 모든 워커는 캐시된(잠재적으로 낡은) 복사본 H̃_j^(ℓ−1)로 되돌아간다. 필요한 블록이 확보되면 각 P(i)가 중간 곱 T_i^(ℓ−1)를 만들고 다음 레이어 임베딩 H_i^(ℓ)를 계산한 뒤, 새 블록이 신선도 한계를 만족하는지에 따라 플래그 F(i)를 갱신한다(Line 17).

그래디언트 클리핑. 역전파에서 그래디언트 블록 δ_j도 유사한 전파 패턴을 따른다. 통신량을 억제하기 위해 국소 그래디언트 클리핑을 적용하며(Line 22), 이는 역사적 임베딩 재사용 시 정규화(regularizer)로도 작용한다. 표준 관행에서 클리핑은 L2 노름이 임계 th를 넘을 때 발동된다. P개 워커의 탈중앙 설정에서는 워커별 임계 th_i를 쓴다 — 워커 간 그래디언트가 분산 σ²의 i.i.d.라면 집계 후 분산은 Pσ²이므로 𝔼‖δ_i‖₂ ≈ σ, 𝔼‖δ‖₂ ≈ P^1/2σ가 된다. 이는 국소 클리핑 임계를 P^1/2로 스케일링하는 th_i = P^1/2 th를 정당화한다. 최종 모델 갱신은 모든 워커의 그래디언트를 집계해 전 랭크에 배포하는 AllReduce로 수행된다.

5.2.3역사적 임베딩

임베딩 행렬 H를 행 방향으로 블록 H_i로 분할해 각 프로세스에 배정한다. 일반 GNN의 레이어-ℓ 임베딩을 구성하려면 개념적으로 모든 GPU의 임베딩 블록 기여를 조립해야 한다. 역사적 임베딩 h̃^(ℓ)의 선행 활용[5, 18]에서 착안해, 이 개념을 분산 GNN 학습으로 확장하여 다른 워커가 생성한 중간 임베딩 블록을 재사용 가능한(그리고 잠재적으로 낡은) 결과로 취급한다. 그 결과 임베딩 행렬 H^(ℓ)는 두 범주의 블록으로 구성된다 — (i) 방금 갱신을 브로드캐스트한 ACTIVE 워커의 신선하게 계산된 부분행렬, (ii) 임베딩 변화가 이 반복에서 무시할 만큼 작은 STALE 워커의 캐시된 역사적 부분행렬이다. 각 GPU는 충분히 신선하다고 간주되는 것만 보유하는 캐시를 유지한다.

H^(ℓ) = σ([H_i^(ℓ−1)]_i=1^P, Â; W^(ℓ−1)) ≈ σ([ H_{i : P(i)⇐ACTIVE}^(ℓ−1) | H̃_{i : P(i)⇐STALE}^(ℓ−1) ]_i=1^P, Â; W^(ℓ−1))EQ 5.1

5.2.4Skip-Broadcast

탈중앙 구조에서 핵심 도전은 워커들이 유계 신선도 아래 역사적 임베딩을 안전하게 재사용할 수 있도록 집합 통신(일대전체 브로드캐스트 등)을 적응시키는 것이다. 통상적 탈중앙 구현[4]은 벌크 동기(bulk-synchronous) 실행 방식을 따르기 때문에 신선한 블록과 낡은 블록을 선택적으로 섞을 여지가 거의 없어 자명하지 않다. 이에 중앙 파라미터 서버에 의존하지 않고 구현이 간단한 경량 통신 프리미티브 Skip-Broadcast를 설계해, 학습 중 통신 토폴로지를 실시간으로 재형성할 수 있게 한다. 워커별 상태 변수 Flag(i)가 그 워커의 임베딩 블록을 브로드캐스트할지 추적한다.

매 반복 검사·갱신되어 링 토폴로지를 지속적·매끄럽게 재형성한다

⟨Fig 5.6⟩ Skip-Broadcast 예시(STALE 워커는 빨강으로 표시). STALE 워커의 전송을 회피함으로써 통신 오버헤드를 한층 낮춘다.

5.2.5유계 임베딩 신선도

Skip-Broadcast가 활성화되면 워커마다 서로 다른 반복에서 생성된 임베딩 블록을 소비해 시스템 전반의 혼합 버전 임베딩 뷰가 발생한다. 이를 통제하기 위해 Sancus는 유계 임베딩 신선도를 강제한다. 유계 그래디언트 신선도에 관한 선행 연구[16, 19, 20]는 주로 SGD를 겨냥해 낡은 그래디언트가 초래하는 해악을 제한해 수렴을 보전하는 것이 목표였다. 이 장의 설정은 근본적으로 다르다 — 낡은 임베딩은 비동기성의 부산물로 감수되는 것이 아니라, 통신을 줄이기 위해 의도적으로 재사용된다. 이를 안전하게 만들기 위해 낡은 임베딩이 유발하는 근사 오차를 명시적으로 정량화·제약하는 지표군 Δ를 도입한다.

DEFINITION 5.2 — EPOCH-FIXED (Δ_E)

낡은 중간 임베딩이 생성된 에폭 인덱스를 ẽ, 현재 에폭을 e라 할 때, 허용 가능한 최대 낡은 에폭 수를 고정 에폭 신선도 예산 Δ_E로 정의한다 — 즉 |ẽ − e| ≤ Δ_E. 이 규칙 아래 모델 계산에 쓰이는 중간 임베딩은 Δ_E 에폭마다 한 번만 브로드캐스트된다.

DEFINITION 5.3 — EPOCH-ADAPTIVE (Δ_A)

각 프로세서 P(i)가 사용하는 임베딩과 그의 모든 인입(in-coming) 이웃 프로세서가 생성한 임베딩 사이의 허용 최대 에폭 격차를 Δ_A로 정의한다. 구체적으로 P(i)는 각 인입 이웃으로부터 최대 Δ_A 에폭 이내의 임베딩을 받은(그리고 재사용한) 후에야 자신의 최신 결과를 브로드캐스트해야 한다.

DEFINITION 5.4 — VARIATION-GAP (Δ_H)

낡은 임베딩의 최대 변동 폭을 제한하는 값 기반 허용치다 — ‖H̃_i^(ℓ) − H_i^(ℓ)‖ ≤ Δ_H. 이 기준에서 중간 임베딩은 변동 폭이 Δ_H를 초과할 때마다 적응적으로 브로드캐스트되며, 몇 에폭이 생략되었는지와는 무관하다.

에폭 고정 규칙은 시스템을 여전히 대체로 동기적으로 행동하게 만들 수 있다. 탈중앙 설정 — 특히 워커의 진행 속도가 서로 다를 때 — 에 더 잘 맞도록, 워커가 적응적으로 선택된 과거 반복의 임베딩을 재사용할 수 있게 하는 두 유연한 지표(Def 5.3·5.4)를 추가 도입해 이기종 실행 속도 아래 더 세밀한 신선도 제어를 가능하게 한다.

유계 신선도 검사 절차 — 탈중앙 버전 관리

기존 분산 ML로부터의 개념적 전환은 신선도 제약이 그래디언트가 아닌 중간 임베딩 H_i에 부과된다는 점이다. 검사는 데이터베이스의 버전 관리 개념[21]에서 착안했으나 완전히 탈중앙 방식으로 구현한다 — 워커 i가 워커 j로부터 최신 블록 H_j를 받을 때마다 그것이 생성된 에폭을 기록하는 국소 버전 태그 Ver_i(j)를 부착하고, 받은 모든 블록에 대해 이 태그를 유지한다. Algorithm 1의 Line 8이 CACHE(H_j)에서 CACHE(H_j, Ver(j))로 최소 변경되면 된다.

ALGORITHM 2 — Def 5.2 기반 검사

Input: 현재 에폭 Ver; 캐시 버전 Ver(j)
1 procedure STALE( )
2 if Ver − Ver(j) ≥ Δ_E then
3 F(i) ← ACTIVE ▷ 한계 초과
4 else F(i) ← STALE ▷ 허용 내
5 end if
6 end procedure

기본 한계는 모든 워커에서 동일하므로 Ver_i(j)의 첨자 i를 생략한다. Δ_E = 1이면 한 에폭 건너 브로드캐스트를 생략한다(Fig 5.7a).

ALGORITHM 3 — Def 5.3 기반 검사

Input: 현재 에폭 Ver; 캐시 버전 Ver_i(j)
1 procedure STALE( )
2 for all P(i) in parallel do
3   for j = 1 to p do
4    ▷ 워커 i가 H̃_j에 대해 한계 초과
5    if Ver − Ver_i(j) ≥ Δ_A then
6     F(j) ← ACTIVE
7     EndProcedure for P(j)
8    end if
9-11 end for / end for / end procedure

버전 태그를 수신자별로 유지한다. i가 j보다 빠르게 진행하면 H̃_j가 과도히 낡았다고 판정해 j에 곧 브로드캐스트를 촉구한다.

ALGORITHM 4 — Def 5.4 기반 검사

Input: P(i)에서 계산된 현재 H_i; 캐시 H̃_i
1 procedure STALE( )
2 if ‖H_i − H̃_i‖ ≥ Δ_H then
3 F(i) ← ACTIVE ▷ 한계 초과
4 else F(i) ← STALE ▷ 허용 내
5 end if
6 end procedure

신선도가 임베딩 변화량만으로 결정되고 판단이 각 워커에서 국소적으로 이루어진다. 명시적 버전 추적이 전혀 필요 없고, 워커는 적응적 수의 에폭 동안 STALE로 남을 수 있다(Fig 5.7c).

Fig 5.7b의 Δ_A = 1 동작 예시. 에폭 9에서 워커 2의 캐시 결과 H₂⁽⁷⁾는 9 − 7 = 2 > Δ_A = 1이므로 허용되지 않아, 워커 2가 ACTIVE로 전환되어 에폭 10에 신선한 임베딩을 브로드캐스트한다. 이어 다른 워커들이 여전히 H₁⁽⁸⁾을 쓰고 있어 한계를 위배하므로 워커 1이 ACTIVE로 표시되고, 마찬가지로 에폭 11에 워커 3·4가 ACTIVE로 지정된다.

5.3

이론적 분석

THEORETICAL ANALYSIS

5.3.1통신 비용 분석

제거 가능한 통신량은 신선도 허용치가 지배한다 — 직관적으로 허용치가 넓을수록 더 많은 브로드캐스트를 생략해 더 큰 절감을 얻는다. 이를 정량화하기 위해 Tripathy 등[4]과 Chan 등[22]의 분석을 따라 표준 α–β 비용 모델을 채택한다 — α는 메시지 크기와 무관한 고정 시작 지연, β는 목적지 워커까지 데이터를 전달하는 워드당 전송 시간(대역폭의 역수)이다. 이 정식화에서 F 워드 메시지 하나를 p 프로세스에 브로드캐스트하는 통신 하한은 O(α + Fβ)이고[4], all-reduce 비용은 O(log p; α + 2((p−1)/p)Fβ)의 하한을 갖는다[22].

신선도가 허용되지 않을 때 순전파의 각 프로세스는 중간 임베딩 블록을 나머지 (p − 1) 프로세스에 브로드캐스트해야 하므로 프로세스당 하한은 (p − 1)(α + (N/p)Fβ)이며, 역전파에서도 대응하는 하한과 (F × F) 행렬에 대한 AllReduce 하한이 더해진다. 따라서 총 통신 비용의 하한은 다음과 같다.

COST_comm = O( L(2(p − 1) + log p)α + 2p − 1pF(N + F)β )EQ 5.2

총 에폭 수를 e_T, Skip-Broadcast가 발동해 역사적 임베딩을 재사용한 에폭 수를 e_R이라 하면, 신선도 인지 병렬 알고리즘의 비용은 자연히 두 성분으로 분리된다 — (1) 신선한 결과를 전송하는 에폭에서는 기준 동작을 따라 Eq 5.2와 일치하고, (2) 역사적 임베딩을 재사용하는 에폭에서는 브로드캐스트 성분이 제거되어 남는 통신이 AllReduce에 지배된다.

COST*_comm = (e_T − e_R)COST_comm + e_RL·COST_ar = L{[2(p−1)(e_T−e_R) + e_T log p]α + 2p−1pF[N(e_T−e_R) + e_TF]β}COST BOUND

이 식은 더 타이트한 통신 한계를 주지만 상대적 절감 폭이 한계식 자체로는 즉시 드러나지 않는다. §5.4.2에서 실험적으로 통신 비용을 최대 74%까지 줄일 수 있음을 보인다.

5.3.2수렴 분석

유계 임베딩 신선도에 기반해 중간 임베딩과 그래디언트의 근사 오차 한계, 그리고 수렴 보장을 확립한다. 즉 통신을 줄이기 위해 역사적 정보를 캐시·반복 재사용하는 것이 유발하는 근사 오차가 신선도 제약 아래 통제 가능함을 보인다. 증명은 다음 단계로 전개된다.

PROPOSITION 5.1 — 기초 부등식 도구

‖A‖_∞ = max_i,j|A(i, j)|이고 col(A)가 행렬 A의 열 수일 때, ‖A + B‖_∞ ≤ ‖A‖_∞ + ‖B‖_∞, ‖A ⊙ B‖_∞ ≤ ‖A‖_∞‖B‖_∞, ‖AB‖_∞ ≤ col(A)‖A‖_∞‖B‖_∞가 성립한다([5], Proposition B). 증명에 등장하는 최대 열 수를 C := max{col(Â), col(H⁽⁰⁾), …, col(H^(L)), col(W⁽⁰⁾), …, col(W^(L))}로 둔다.

LEMMA 5.1 — 중간 결과의 근사 오차 한계

각 프로세스가 레이어 ℓ에서 N/p개 입력 활성 H̃_i^(ℓ)를 사용하는 탈중앙 설정에서, (1) 활성 함수 σ(·)가 ρ-립시츠 연속이고, (2) Â_i, H̃_i, H_i, W_i의 성분이 상수 B로 유계이며, (3) 역사적 임베딩이 신선도 예산 내에서 정확한 임베딩을 근사(‖H̃_i^(ℓ) − H_i^(ℓ)‖ ≤ Δ_H)한다고 가정하면, 중간 출력의 근사 오차도 유계다.

‖T̃_i^(ℓ) − T_i^(ℓ)‖_∞ ≤ pCBΔ_H ‖Z̃_i^(ℓ) − Z_i^(ℓ)‖_∞ ≤ C²B²Δ_H

증명 요지 — 워커가 쓰는 블록 H̃_i는 최신 H_i이거나 이전 에폭의 스냅숏 H_s이며, 후자의 재사용은 편차가 ‖H_i − H_s‖ ≤ Δ_H로 유계일 때만 허용된다. Proposition 5.1을 ‖Σ_jÂ_ij(H̃_j − H_j)‖에 적용하면 첫 부등식을, ‖Â_i(H̃_i − H_i)W_i‖에 적용하면 둘째 부등식을 얻는다.

LEMMA 5.2 — 그래디언트의 근사 오차 한계

임의 프로세스 P(i)에서 (1) 활성 σ(·)와 손실 그래디언트 ∇ℒ이 ρ-립시츠 연속이고 (2) Â_i, W_i, δ^(ℓ), σ′(Z_i)가 상수 B로 균일 유계이면, 낡은 중간 상태가 유발하는 그래디언트 오차는 유계다 — ‖∇_{Z̃_i^(ℓ)}ℒ̃ − ∇_{Z_i^(ℓ)}ℒ‖ ≤ Δ_K, ‖∇_{W̃_i^(ℓ)}ℒ̃ − ∇_{W_i^(ℓ)}ℒ‖ ≤ Δ_K. 여기서 Δ_K는 ρ, C, B, Δ_H가 결정하는 상수다.

증명 요지 — 레이어에 대한 수학적 귀납법으로 진행한다. 기저(ℓ = L): ∇ℒ의 ρ-립시츠성과 Lemma 5.1로 ‖·‖_∞ ≤ ρ‖Z̃_i^(L) − Z_i^(L)‖_∞ ≤ ρC²B²Δ_H = Δ_K^(L). 귀납 단계: 역전파 점화식과 Proposition 5.1, Lemma 5.1을 결합해 Δ_K^(ℓ) = C²B³(Δ_K^(L) + Δ_K^(ℓ+1))로 두면 부등식이 레이어 ℓ에서도 유지된다. ∇_Wℒ̃에 대한 한계도 유사한 논증으로 따라온다.

THEOREM 5.1 — 수렴 보장

국소 최소점 W*, 초기값 W⁽¹⁾, 신선도 예산 Δ_H를 갖는 L-레이어 GNN에서 (1) σ(·)와 ∇ℒ이 ρ-립시츠 연속, (2) ‖∇_Wℒ̃‖_∞, ‖∇_Wℒ‖_∞, ‖ℒ(W)‖_∞가 모두 상수 G > 0으로 유계, (3) 손실 ℒ(W)가 ρ-매끄러움을 만족하면, 어떤 상수 K > 0이 존재해 임의의 N > LΔ_H에 대해, 유계 신선도로 최대 N 반복 병렬 학습하고 인덱스 R ∈ [1, …, N]을 균등 무작위로 택할 때 다음이 성립한다.

𝔼_R[‖∇ℒ(W^(R))‖²_F] ≤ 2·ℒ(W⁽¹⁾) − ℒ(W*) + ρ2K√N, η = min{1ρ, 1√N}EQ 5.3

ℒ의 ρ-매끄러움과 Lemma 5.2로부터 ℒ(W⁽ⁱ⁺¹⁾) ≤ ℒ(W⁽ⁱ⁾) − (η − (ρ/2)η²)‖∇ℒ(W⁽ⁱ⁾)‖²_F + (ρ/2)η²K (Eq 5.4)를 얻고, 모든 i에 대해 합해 정리한 뒤(Eq 5.5) 양변을 N(η − (ρ/2)η²)로 나누면 Eq 5.3이 도출된다. 특히 N → ∞일 때 𝔼_R‖∇ℒ(W^(R))‖²_F → 0이므로 수렴이 보장된다.

※ 지면 제약으로 더 엄격한 조건인 Definition 5.4에 대해서만 분석을 제시한다. 기본 고정 에폭 신선도에 대한 이론적 결과는 Δ_H = max|ΔH| × Δ_E로 두면 계로서 따라온다(max|ΔH|는 H의 에폭당 최대 변동 폭). 증명 전략은 ([5], Theorem 2)를 따르지만 직접적 재사용은 아니다 — (1) 샘플링 없는 전체 그래프 풀배치 학습을 다루고, (2) 중앙집중이 아닌 탈중앙 병렬 설정에서 학습하며, (3) 낡은 활성을 1에폭으로 제한하는 다수 선행 접근과 달리 생략 에폭 수가 자동 결정되는 적응적 재사용을 허용한다는 점에서 본질적으로 다르다.

5.4

실험

EXPERIMENTS

네 가지 핵심 질문에 답한다 — (1) 서로 다른 시스템 구성에서 Sancus는 얼마나 효과적으로 통신을 줄이며 최신 기법과 어떻게 비교되는가, (2) 신선도 인지 재사용으로 모델 정확도를 보전하면서 통신을 낮출 수 있는가, (3) 실제 생략 에폭 패턴은 어떤 모습이며 신선도를 효과적으로 관리하도록 적응하는가, (4) 역사적 임베딩 캐싱이 유발하는 메모리 오버헤드는 얼마인가.

5.4.1데이터셋과 구현

데이터셋	도메인 · 태스크	\|𝒱\|	\|ℰ\|	\|F\|	#Class	바이트 크기
Flickr	공통 속성을 공유하는 이미지 간 관계 · 단일 클래스	89,250	899,756	500	7	529 MB
Reddit	게시물·사용자 댓글, 게시물의 주제 커뮤니티 예측 · 단일 클래스	232,965	11,606,919	602	41	3.53 GB
Amazon	동일 고객이 공동구매한 상품 · 다중 클래스	1,598,960	132,169,734	200	107 (m)	2.34 GB
ogbn-products	상품 공동구매 네트워크 · 다중 클래스	2,449,029	61,859,140	100	47	1.38 GB
ogbn-papers100M	인용 네트워크, 논문의 주제 영역 예측 · 다중 클래스	111,059,956	1,615,685,872	200	172	56.2 GB

⟨Table 5.2⟩ 실험에 쓰인 그래프 데이터 통계("m": 다중 클래스 분류). 모든 데이터셋은 고정 분할(fixed-partition split)[24, 25]을 사용한다.

구현과 변형. 분산 GNN 학습에 적응된 고전적 탈중앙 병렬 알고리즘[15]의 PyTorch[26] 구현[4] 위에 Sancus를 구축한다. Def 5.2의 고정 에폭 한계 Δ_E는 Algorithm 1 + 2로 구현해 SCS-E, Def 5.3의 에폭 적응 한계 Δ_A는 Algorithm 1 + 3으로 구현해 SCS-A, Def 5.4의 변동 폭 한계 Δ_H는 Algorithm 1 + 4로 구현해 SCS-H라 한다. 또한 전통적 분산 학습의 유계 그래디언트 신선도를 적용한 SkipG[27]를 구현해, 이 설정에서는 유계 임베딩 신선도가 더 효과적임을 보인다. 세 필수 구성요소는 역사적 임베딩 캐시, 유계 신선도 검사기를 갖춘 버전 컨트롤러, Skip-Broadcast 연산자다. 통상 관행[5, 18, 28]에 따라 학습 초기의 큰 임베딩 변동과 공격적 재사용의 악영향을 피하고자 브로드캐스트를 생략하지 않는 워밍업 에폭 50회를 모든 데이터셋에 포함한다.

하드웨어 구성. ① PCIe 3.0×16으로 연결된 RTX 2080 Ti 8장, ② 10 Gbps 이더넷으로 연결된 서버 2대(각 PCIe 3.0의 RTX 2080 Ti 4장), ③ NVLink로 상호 연결된 A100 40 GB 4장, ④ NVLink로 상호 연결된 V100 32 GB 4장. Flickr·Reddit·Amazon·ogbn-products는 ①에서, ogbn-products는 추가로 ①②③에서, 최대 데이터셋 ogbn-papers100M은 ③에서 실행하며, 최신 시스템과의 엔드투엔드 비교[2–4, 6, 29]에는 널리 채택된 ④를 쓴다. 모델은 3 또는 4 레이어 GCN[1](은닉 차원: Flickr·Reddit 16, Amazon 256, ogbn-products 128, ogbn-papers100M {16, 32, 64})이며 일반성 검증을 위해 GAT[30]도 구현한다. 총 학습 에폭 e_T는 각각 300/300/400/500/200이고, 신선도 제어는 Δ_E ∈ [1, 7], Δ_A ∈ [1, 5], Δ_H ∈ [0.01, 0.05] 범위를 훑는다.

5.4.2통신 효율 평가

vs CAGNET · SkipG

추가 35–74% 통신 절감

정확도 손실이 0.01 이내인 구성을 보고할 때(Fig 5.8), 최신 탈중앙 베이스라인 CAGNET과 유계 그래디언트 방식 SkipG 대비 모든 Sancus 변형이 유계 임베딩 신선도를 통해 추가 35~74%의 통신을 절감한다. SkipG도 그래디언트 브로드캐스트 생략으로 CAGNET보다 통신을 줄일 수 있으나 모델 품질에 대한 신선도 인지 안전장치가 없어 통신을 정확도와 교환한다 — 최대 5%의 정확도 하락을 겪는(Fig 5.10) 반면 Sancus는 모든 데이터셋에서 정확도를 유지한다. Sancus는 SkipG보다도 데이터셋에 따라 추가 29~63%를 더 절감한다.

BEST CASES

Flickr 74% · Reddit 48% · products 50%

가장 강한 결과로 Flickr에서 약 74%(SCS-H3, Δ_H = 0.03), Reddit에서 48%(SCS-A3), ogbn-products에서 50%(SCS-H3)의 통신을 줄인다. SCS-E도 통신 회피 면에서는 경쟁력 있게 보이지만 Δ_E가 커질수록 정확도가 급격히 악화되며(Fig 5.10b·5.11a·5.12b), 더 적응적인 SCS-A/H 변형과 대비된다.

Amazon과 ogbn-papers100M의 35% 절감이 상대적으로 완만해 보이는 이유는 두 설정이 본질적으로 훨씬 큰 통신량을 수반하기 때문이다 — Amazon은 정확도 유지를 위해 4-레이어 · 은닉 256의 더 깊고 넓은 GNN을 쓰고, ogbn-papers100M은 실험군 최대 데이터셋이다.

SYSTEM VARIANTS · FIG 5.9

4개 축 전반의 강건성

가장 절감이 작은 보수적 변형 SCS-E1/A1/H1로 일반성을 평가한다. (a) GPU 구성 — 통신 시간이 구성마다 크게 다르지만 ①②③ 모두에서, 다중 GPU 단일 노드와 다중 서버 배포를 아울러, GPU 종류가 달라도 안정적 절감을 제공한다. (b) GPU 수 — GPU가 늘수록 CAGNET 대비 총 학습 비용이 계속 감소한다. 원 통신량은 GPU 수와 함께 증가하지만 SCS-H가 이를 실질적으로 완화해, 8 GPU에서의 통신 비용이 CAGNET의 2 GPU 수준에 근접하면서 계산 비용도 67% 절감한다. 특히 Sancus가 제거하는 통신 비율이 GPU 수와 함께 증가하는데, 이는 중앙집중 PS 구조가 좇기 어려운 확장 거동이다[14]. (c) 레이어 수와 (d) 은닉 차원 — 깊이가 달라도 통신 회피가 유지되고, 은닉 차원을 키울 때 CAGNET 대비 통신 증가가 더 느리고 작다.

구성	연산	CAGNET	SCS-A1	SCS-E	SCS-H
① 8×1 · p2p 없음	Compute	0.365	0.359	0.359	0.343
① 8×1 · p2p 없음	Communicate	1	0.687	0.697	0.675
② 4×2 · p2p 없음	Compute	0.093	0.093	0.092	0.090
② 4×2 · p2p 없음	Communicate	1	0.717	0.714	0.698
③ 4×1 · p2p 있음	Compute	0.437	0.431	0.431	0.425
③ 4×1 · p2p 있음	Communicate	1	0.703	0.708	0.692

⟨Table 5.3⟩ Reddit에서 1 에폭의 상세 시간 분해(초, 통신은 CAGNET = 1로 정규화된 값으로 보고됨). 다중 서버 환경을 포함한 세 환경 전반에서 SCS-A1이 일관되게 가장 작은 총 오버헤드를 발생시킨다.

5.4.3학습 효율 평가

시스템	구성	처리량 (epochs/s)	출처
SCS-A (Sancus)	V100 × 4	1000/97.4 = 10.3	—
CAGNET[4]	V100 × 4	1 × 4.9 ≈ 5	Fig. 1 [4]
RoC[3]	P100 × 4	~(1000/150) = 7	Fig. 5 [3]
Dorylus[6]	Lambda on CPU × 2	130/860 = 0.15	Sect. 7.2 Table [6]
PaGraph[29] (샘플링 기반)	1080ti × 4	1/0.11 = 9	Sect. 5.2 · 5.5; Fig. 9 [29]
DGCL[2]	V100 × 4	5	Fig. 8(a) [2]

⟨Table 5.4⟩ Reddit에서 GCN의 처리량(epochs/second). 주 (1) RoC 결과의 P100(4.7 TFLOPs)은 V100(7 TFLOPS)의 67% 속도. (2) Dorylus는 130 에폭에 $0.085/h × 860 s = $0.2, SCS-A는 $3.06/h × 4 × 13 s = $0.04. (3) PaGraph는 샘플링 기반이다. 각 시스템에 대해 직접 비교 가능한 최선의 공개 구성을 보고한다.

비교 대상은 각기 정교한 설계를 갖는다 — RoC는 정교한 메모리 관리를, PaGraph는 고차수 노드의 정적 GPU 캐싱을 도입하며 둘 다 워크로드 균형과 크로스 디바이스 접근 절감을 위해 자명하지 않은 분할에 의존한다. Dorylus는 유계 신선도 비동기성으로 CPU 서버 기반 저비용 분산 학습을 가능하게 하고, DGCL은 시스템 토폴로지에 최적화된 노드별 경로를 계산해 통신을 줄인다. 통신 절감이 가장 작은 보수적 변형 SCS-A1으로도 Sancus는 비교된 모든 최신 시스템을 능가한다 — 최대 10.3 epochs/s에 도달해 평균 1.86× 처리량 개선을 제공하며, 저비용 풀배치 분산 학습을 겨냥한 Dorylus 대비 68.7× 빠르면서 비용은 80% 적다.

5.4.4모델 성능 평가

ACCURACY · FIG 5.10 · 5.12b

0.005 이내의 정확도, 더 빠른 실질 수렴

역사적 임베딩을 반복 재사용하고 Skip-Broadcast를 적응적으로 호출하면서도 GNN 정확도를 유지한다. 제안된 모든 변형이 CAGNET에 극히 근접한 정확도(0.005 이내)로 수렴하며, 통신을 회피했음에도 일부 경우 베이스라인과 같거나 약간 상회한다. 나아가 만족스러운 정확도 수준에 눈에 띄게 더 일찍 도달해 실질적 수렴이 빠르다. 반면 전통적 유계 그래디언트 방식 SkipG는 임베딩 기반 skip-broadcast 전략보다 훨씬 큰 정확도 저하(최대 0.02)를 보인다. 이 실증 관찰은 §5.3.2의 이론적 결과와 정합한다.

STALENESS-AWARE · FIG 5.12a

비균일 브로드캐스트 스케줄

대조군인 에폭 고정 변형 SCS-E1은 두 반복마다 한 번 브로드캐스트하므로 캐시 에폭이 완벽히 규칙적인 패턴으로 증가한다. 반면 에폭 적응 변형 SCS-A·SCS-H는 명백히 비균일한 브로드캐스트 스케줄을 보이며 연속 지점 간 간격이 학습 전반에서 변하는데, 이 불규칙성은 SCS-H에서 특히 두드러진다 — 변동 폭 기준에서 생략 에폭 수가 허용치 Δ_H에 의해 동적으로 결정되기 때문이다.

보수적 설정 SCS-E1/A1/H1이 가장 적은 에폭을 재사용해 절감이 가장 작다(Fig 5.8과 일치). 결정적으로 에폭 고정 SCS-E 계열 대비 적응 전략이 더 높은 정확도를 달성해, 시스템 신선도를 명시적으로 관리하는 것이 효과성을 더 잘 보전함을 시사한다. SCS-E3가 이를 강조한다 — 유사한 수의 에폭을 캐시하고 유사한 통신 절감을 얻지만 정확도 손실은 가장 크다.

캐시 메모리 풋프린트 (구성 ①)	2 GPUs	4 GPUs	8 GPUs
Flickr (MB)	297.9	255.3	170.2
Reddit (GB)	0.9	0.8	0.5
Amazon (GB)	2.1	1.8	1.2
ogbn-products (GB)	1.6	1.4	0.9

⟨Table 5.5⟩ 역사적 임베딩 캐시의 메모리 풋프린트. Sancus의 GPU 메모리 사용은 (i) 로컬 데이터(임베딩·로컬 인접 부분행렬·복제 가중치), (ii) 행렬 연산용 임시 작업 공간, (iii) 역사적 임베딩 캐시에서 온다. CAGNET 대비 추가되는 유일한 메모리는 (iii)이며, 대부분 데이터셋에서 현대 GPU 가용 메모리의 작은 일부만 차지한다. ogbn-papers100M은 4 GPU에서만 실행되며 캐시 크기는 31 GB로 표에서 제외했다.

일반화 용이성. GCN을 넘어 다른 풀그래프 아키텍처 GAT[30]에 적용해도(Fig 5.13a·b) 정확도를 유지하며 통신을 계속 줄인다(GAT의 절대 정확도는 광범위한 하이퍼파라미터 튜닝이 이 연구 범위를 벗어나므로 완전히 최적화되지 않았다). 선행 연구[4]에서 1D와 1.5D가 가장 효과적인 구성으로 보고되므로 1.5D CAGNET 결과도 포함한다 — Sancus가 최소한의 정확도 영향으로 통신을 여전히 줄이되, 하부 1.5D 알고리즘이 이미 브로드캐스트를 더 적게 수행하므로 1.5D에서의 이득은 더 작다.

5.4.5유계 신선도의 효과

신선도 하이퍼파라미터에 대한 민감도를 조사한다(Fig 5.11 — Δ_E는 a, Δ_A는 b, Δ_H는 c·d). 한계가 커질수록 학습 궤적의 변동성과 요동이 커지는 경향이 있다. 느슨한 한계는 반복 수 기준 수렴을 늦출 수 있으나, 더 많은 브로드캐스트를 생략하므로 엔드투엔드 학습 시간은 여전히 감소할 수 있다. 동시에 한계 확대는 통상 더 큰 통신 절감을 낳으면서(Fig 5.8) 평가 범위 내에서 정확도 손실은 무시할 만하다(Fig 5.10). 종합하면 Δ_E, Δ_A, Δ_H는 목표 응용의 필요에 맞춰 조정할 수 있다 — 작은 한계는 정확도를, 큰 한계는 효율을 우선한다.

분산 학습에서 실행시간–오차 트레이드오프의 이해는 본질적으로 어렵다. 시스템 효과(통신, 낙오자)와 학습 역학(수렴 거동)이 긴밀히 얽혀 있기 때문이다. 원리상 큰 신선도 허용은 처리량을 높이지만 정확도를 훼손할 수 있고[16, 19, 31–33], 실현되는 신선도는 응용·데이터셋·구현 세부·하드웨어·소프트웨어 구성에 의존한다. 데이터셋마다 한계 변화에 다르게 반응하지만(Fig 5.11a·d) 모든 실험에서 무시할 만한 수렴 지체로 만족스러운 모델 품질을 얻을 수 있었다. 이 트레이드오프의 완전한 규명은 여전히 열린 연구 문제[31, 32]이나, 이 GNN 학습 설정에서는 Δ_A = {2, 3}과 Δ_H = {0.02, 0.03}의 적응 전략이 실행시간과 정확도 사이의 실용적·효과적 균형을 제공한다.

5.5

결론

CONCLUSION

이 장은 역사적 임베딩 캐싱을 통해 통신을 적응적으로 줄이면서, 유계 임베딩 신선도로 시스템 신선도를 통제하고 모델 성능을 보전하는 최초의 신선도 인지 통신 회피 탈중앙 GNN 학습 접근 Sancus를 제시했다. 세 가지 유계 임베딩 신선도 지표 — 에폭 고정 신선도, 에폭 적응 신선도, 에폭 적응 변동 폭 신선도 — 를 도입하고, 이에 기반해 탈중앙 GNN 학습에 역사적 임베딩 캐시와 유계 신선도 검사기를 결합함으로써 GPU들이 브로드캐스트를 적응적으로 건너뛸 수 있게 했다. 워커는 지정된 한계 내에 머무는 동안 캐시된 역사적 임베딩을 재사용하고, 예산이 위배되면 최신 임베딩을 브로드캐스트하며 캐시를 갱신한다. 나아가 통신 비용과 근사 오차 양쪽에 대한 이론적 한계를 제공하고, 대규모 벤치마크 그래프에서 광범위한 실험으로 효율성과 효과성 및 신선도 관리에서 적응성이 갖는 중요성을 검증했다. 마지막으로 메모리 풋프린트 보고를 통해 역사적 임베딩 캐싱이 메모리 효율적임을 보였다.

REF

참고문헌

CHAPTER 5 · 33 REFERENCES

[1] Kipf & Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks (GCN). ICLR.
[2] Cai et al. 2021. DGCL: an efficient communication library for distributed GNN training. EuroSys.
[3] Jia et al. 2020. Improving the Accuracy, Scalability, and Performance of GNNs with Roc. MLSys.
[4] Tripathy et al. 2020. Reducing communication in graph neural network training (CAGNET). SC.
[5] Chen et al. 2018b. Stochastic Training of GCNs with Variance Reduction. ICML.
[6] Thorpe et al. 2021. Dorylus: Affordable, Scalable, and Accurate GNN Training with Distributed CPU Servers and Serverless Threads. OSDI.
[7] Wang et al. 2020. GNN-PIM: A processing-in-memory architecture for graph neural networks. ACA.
[8] Gandhi & Iyer. 2021. P3: Distributed Deep Graph Learning at Scale. OSDI.
[9] Ma et al. 2019. NeuGraph: Parallel Deep Neural Network Computation on Large Graphs. USENIX ATC.
[10] Min et al. 2021. Large GCN Training with GPU-Oriented Data Communication Architecture. PVLDB.
[11] Zheng et al. 2020. DistDGL: Distributed GNN Training for Billion-Scale Graphs.
[12] Zhu et al. 2019. AliGraph: A Comprehensive Graph Neural Network Platform. PVLDB 12(12).
[13] Li et al. 2015. MALT: distributed data-parallelism for existing ML applications. EuroSys.
[14] Lian et al. 2017. Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel SGD. NeurIPS.
[15] Gholami et al. 2018. Integrated Model, Batch, and Domain Parallelism in Training Neural Networks. SPAA.
[16] Cipar et al. Solving the Straggler Problem with Bounded Staleness. HotOS XIV.
[17] Karypis & Kumar. 1998. A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs (METIS). SIAM J. Sci. Comput. 20(1).
[18] Fey et al. 2021. GNNAutoScale: Scalable and Expressive GNNs via Historical Embeddings. ICML.
[19] Jiang et al. 2017. Heterogeneity-aware Distributed Parameter Servers. SIGMOD.
[20] Xian et al. 2021. H-PS: A Heterogeneous-Aware Parameter Server With Distributed Neural Network Training. IEEE Access 9.
[21] Kim & Lochovsky (Eds.). 1989. Object-Oriented Concepts, Databases, and Applications (버전 관리). ACM Press & Addison-Wesley.
[22] Chan et al. 2007. Collective communication: theory, practice, and experience (α–β 모델). Concurr. Comput. Pract. Exp. 19(13).
[23] Abadal et al. 2022. Computing Graph Neural Networks: A Survey from Algorithms to Accelerators. ACM Comput. Surv. 54(9).
[24] Zeng et al. 2020. GraphSAINT: Graph Sampling Based Inductive Learning Method. ICLR.
[25] Hu et al. Open Graph Benchmark: Datasets for Machine Learning on Graphs. NeurIPS.
[26] Paszke et al. PyTorch: An Imperative Style, High-Performance Deep Learning Library. NeurIPS.
[27] Miao et al. 2021. Heterogeneity-Aware Distributed Machine Learning Training via Partial Reduce (SkipG). SIGMOD.
[28] Cong et al. 2020. Minimal Variance Sampling with Provable Guarantees for Fast Training of GNNs. KDD.
[29] Lin et al. 2020. PaGraph: Scaling GNN training on large graphs via computation-aware caching. SoCC.
[30] Velickovic et al. Graph Attention Networks (GAT). ICLR 2018.
[31] Dai et al. 2019. Toward Understanding the Impact of Staleness in Distributed Machine Learning. ICLR.
[32] Lee & Kim. 2019. Empirical Investigation of Stale Value Tolerance on Parallel RNN Training. ISPASS.
[33] Luo et al. 2020. Prague: High-Performance Heterogeneity-Aware Asynchronous Decentralized Training. ASPLOS.