배경
BACKGROUND
동적 그래프는 소셜 네트워크, 인용 네트워크, 전자상거래, 추천 시스템 등 다수 환경에서 근본적이며, 통상 실세계 과정을 노드 간 타임스탬프가 부여된 상호작용으로 표현한다. Reddit 같은 소셜 플랫폼에서 사용자는 댓글이나 팔로우로 참여하고, 전자상거래에서 고객은 구매를 통해 상품과 상호작용한다. 시간적 링크 예측과 추천 같은 태스크를 지원하려면 노드·간선이 시간에 따라 변하는 진화 그래프 위에서 표현을 학습해야 한다. 반면 다수의 선행 방법[1–4]은 정적 그래프를 가정하며, 시간적 진화를 무시하고 동적 그래프에 적용하면 열등한 성능으로 이어진다는 것이 밝혀졌다[5, 6].
T-GNN[5–9]은 지정된 타임스탬프에서 재귀적 시간적 메시지 패싱으로 노드 표현을 계산한다. 시간 인지 이웃 샘플링과 시간 조건 이웃 집계로 정보 확산이 시간에 따라 어떻게 진화하는지 포착하며, 동적 그래프 예측 태스크에서 정적 GNN[3, 10, 11]과 스냅숏 기반 방법[12–14] 양쪽을 실질적으로 능가한다고 보고된다.
통상 T-GNN은 상호작용의 시간순을 따라 오프라인 학습된다[5, 6]. CPU 메모리에 저장된 입력 동적 그래프를 전처리에서 다수 배치로 분할하며, 각 배치는 타임스탬프 오름차순 상호작용 시퀀스다. 동적 그래프의 시간적 의존성을 유지하기 위해 GPU가 배치를 차례로 처리하고, 각 배치는 시간적 이웃 샘플링 → 입력 데이터 접근 → 모델 계산의 세 단계를 거친다.
그러나 대규모 동적 그래프에서 T-GNN 학습은 극히 자원 집약적이어서 단일 에폭이 수 시간에 이를 수 있다[15]. 이를 완화하려는 최근 노력 — Orca[16]는 역사적 임베딩으로 중복 연산을 건너뛰고, Zebra[15]는 시간적 개인화 PageRank 기반 집계로 가장 영향력 있는 이웃만 선택 집계 — 는 모델 계산 단계에 국한되며 동기식 T-GNN 아키텍처[5, 6, 9]만 지원한다. 반면 TGL[17]은 폭넓은 T-GNN과 호환되는 범용 프레임워크지만 주로 샘플링 단계만 가속하고 다른 성능 결정 단계를 간과한다. 기존 해법이 공유하는 두 핵심 한계는 (1) 전처리에서 통용되는 작은 배치 크기가 모델 계산 효율을 크게 제한하는 것과 (2) 입력 데이터 적재가 전체 학습 시간의 상당 부분을 소비하는 것이다.
효율 병목
EFFICIENCY BOTTLENECKS
⟨Fig 6.1 · Example 1⟩ 배치 3의 두 상호작용 (v4, v2, e42(t5), t5)와 (v4, v5, e45(t6), t6)는 동시 발생으로 취급되어, v4의 시간적 관점에서 t5의 상호작용이 무시된다.
전처리의 부적합한 배칭 방식
선행 연구[6, 8, 15–17]의 전통적 배칭은 통상 작은 배치 크기를 채택해 GPU에서 동시 처리되는 상호작용 수가 제한되고, 이 저활용이 T-GNN의 계산 효율을 저해한다[9]. 그러나 이 방식에서 배치 크기를 단순히 늘리면 배치 내 정보 손실이 증폭된다(Example 1). 실무에서 큰 배치는 GPU 활용률을 높이고 학습을 가속하지만 예측 정확도를 실질적으로 떨어뜨린다. 따라서 정보 손실을 정량화하는 원리적 방법과, 손실 악화를 완화하면서 큰 배치를 가능하게 하는 재설계된 배칭 방식이 필요하다.
압도적인 데이터 적재 오버헤드
입력 데이터 적재가 최우선 병목으로 전체 학습 시간의 약 70%를 차지한다(Fig 6.2). 통상 파이프라인[15–17]은 샘플링 결과에 따라 필요한 모든 데이터를 직접 회수한다 — 샘플된 노드·간선 ID를 그대로 반영한 접근 리스트를 만들고 대응 데이터를 CPU에서 GPU로 전송한다. 단순하지만 T-GNN 학습의 데이터 접근 패턴을 고려하지 않아 심각한 중복을 낳는다.
핵심 관찰은 하나의 배치 안에서도 노드가 서로 다른 타임스탬프의 여러 상호작용에 참여할 수 있다는 것이다. 모델은 시점별 상태 벡터·임베딩을 산출하지만, 이 등장들은 여전히 동일한 하부 입력(노드 특징과 과거 상태 벡터)에서 구축된다. 실제 워크로드에서 이 중복은 전체 적재량의 80% 이상에 이를 수 있다(Fig 6.3).
준최적 데이터 배치 전략
하이브리드 CPU–GPU 배치는 정적 GNN 학습 가속에 매우 효과적임이 입증되었다[20–22] — 전체 입력의 약 1~10%만 학습 전 GPU에 사전 적재해 데이터 적재의 70% 이상을 우회할 수 있다[20]. 그러나 기존 캐싱 선정 기준(높은 in-degree[23], 높은 PageRank[24])은 정적 노드 특징에 초점을 둔다. T-GNN은 오프라인 학습이므로 출현 빈도를 사전 계산해 최빈 항목을 캐싱할 수 있으나, 이 정적 접근은 2.7~36.9%의 적재 절감에 그친다(Fig 6.5) — 동적 그래프의 시간성이 출현 빈도의 멱법칙 분포 가정을 무력화하기 때문이다(LastFM에서 상위 1% 최빈 입력이 전체 출현의 4.2%만 차지).
반대로 동적 하이브리드 배치는 시간 정보를 통합해 타임스탬프 기반으로 GPU 버퍼 내용을 계속 갱신함으로써 더 큰 절감을 얻을 수 있다. 다만 언제·어떻게 갱신하는가가 과제다. LRU[25]는 시간적 지역성을 고려하지만 오프라인 학습 데이터의 전역 출현 패턴을 무시해, 실증 평가에서 정적 배치 대비 미미한 개선만 보였다.
배치별 구성과 데이터 중복 제거
PER-BATCH COMPOSITION AND DATA DEDUPLICATION
ETC6.3.1정보 손실 유계 배칭 방식
ETC의 배칭 전략은 정보 손실을 효과적으로 완화하면서 더 큰 배치를 가능하게 해, 성능 희생 없이 모델 계산 효율을 실질적으로 개선한다. 먼저 배치 Bi의 정보 손실 점수 β(Bi)를 정의한다.
𝒩i는 배치 Bi에 관여한 노드 집합이다. Eq 6.2는 실제 갱신 횟수와 이상적 경우(배치당 노드별 상호작용 1회)의 불일치를 포착하고, Eq 6.1은 노드별 손실을 집계해 배치 전체 손실을 정량화한다. 이로부터 간결한 동등 형태 Eq 6.3이 유도된다.
상호작용 집합 𝒢 = {α(t1), α(t2), …, α(te)}가 주어졌을 때, 이를 K개 배치 B1, …, BK로 분할한다. 각 배치는 상호작용의 연속 구간 Bi = ∪l=pq−1{α(tl)}(p < q)이며 정보 손실 점수 β(Bi)를 갖는다. 목표는 다음을 만족하는 유효 분할 f(𝒢)를 찾아 minf K를 달성하는 것이다.
(6.4) β(Bi) ≤ ε, ∀i · (6.5) Bi ∩ Bj = ∅, i ≠ j · (6.6) ∪i=1KBi = 𝒢 · (6.7) tm < tn, ∀α(tm) ∈ Bi, ∀α(tn) ∈ Bj, i < j
(6.4)는 배치별 정보 손실이 임계 ε을 넘지 않게, (6.5)·(6.6)은 분할의 상호 배타성과 완전성을, (6.7)은 원 동적 그래프의 시간 순서 보존을 강제한다. 상호작용 수가 고정이므로 배치 수 최소화는 배치 크기 최대화와 동등하다.
ALGORITHM 1 — SINGLE-PASS BATCH SPLIT
Input: 동적 그래프 𝒢; 정보 손실 임계 ε / Output: 배치 B₁, B₂, …, B_K1 갱신 카운터 초기화: C_u ← 0
2 배치 ID 초기화: i ← 0
3 빈 노드 집합 초기화: N ← { }
4 빈 배치 초기화: B_i ← { }
5 for α(t) ∈ 𝒢 do ▷ 상호작용을 시간순으로 순회
6 C_u ← C_u + 2
7 for v ∈ α(t) do N ← N ∪ {v} end for
10 β(B_i) ← C_u − |N|
11 if β(B_i) ≤ ε then ▷ 현재 배치 유지
12 B_i ← B_i ∪ {α(t)}
13 else ▷ 새 배치 개시
14 i ← i + 1; C_u ← 0; B_i ← {α(t)}; N ← {v ∈ α(t)}
18 end if
19 end for
각 상호작용을 정확히 한 번 처리하고 배치를 온라인으로 결정하므로 총 실행시간은 O(|ℰ|)이다.
이 문제는 고전적 빈 패킹 문제[26]의 시간순 변형으로 정식화된다. Algorithm 1은 활성 배치에 상호작용을 잠정 삽입하고 손실 점수를 재계산해, 한계를 만족하면 같은 배치에 유지하고 위반하면 새 배치를 열어 그곳에 배정하는 단일 패스 절차다. 단순함에도 최적해를 달성함을 증명할 수 있다.
p번째부터 q번째 직전까지 걸치는 배치 B(p, q)에 대해 β(B(p, q)) ≤ β(B(p, q+c)) (Eq 6.8), β(B(p−c, q)) ≤ β(B(p, q)) (Eq 6.9)가 성립한다.
증명 요지 — Eq 6.3에서 β(B(p, q+c)) − β(B(p, q)) = 2c − (|𝒩(p, q+c)| − |𝒩(p, q)|)를 얻는다. 𝒩(p, q) ⊆ 𝒩(p, q+c)이고 c개의 추가 상호작용이 가져올 수 있는 새 노드는 최대 2c개이므로 우변은 비음(non-negative)이다. 즉 배치에 상호작용을 덧붙이면 β는 증가하거나 최선의 경우 불변이다.
Lemma 2. e(·)를 배치에 포함된 마지막 상호작용의 인덱스라 하면, 모든 0 < i ≤ K에 대해 e(i, OPT) ≤ e(i, ALG1)이 성립한다. 귀납법으로 증명한다 — 기저(i=1)에서 OPT가 ALG1보다 많은 상호작용을 첫 배치에 넣으면 동일 제약을 위반해 실현 불가능해진다. 귀납 단계는 두 경우로 나뉘며, e(i+1, OPT) > e(i, ALG1)인 경우 Lemma 1에 의해 ALG1의 (i+1)번째 배치를 e(i+1, OPT)까지 확장해도 제약을 만족하므로 결론이 따라온다.
Theorem 1. Algorithm 1은 배치 분할 문제의 최적해를 반환한다. OPT가 K* 배치를 쓴다면 e(K*, OPT) = |ℰ|이고 Lemma 2로 e(K*, OPT) ≤ e(K*, ALG1)이며, ALG1도 시퀀스를 한 번 훑어 마지막 상호작용에서 멈추므로 e(K*, ALG1) = |ℰ|다. 따라서 ALG1은 K*보다 많은 배치를 쓸 수 없고 K = K*다.
6.3.2중복 인지 데이터 적재 — Supra
⟨Fig 6.4 · 6.6⟩ 통상 접근 정책의 중복과 Supra 3단계 정책, 그리고 배치 간 파이프라인. Supra는 R개 고유 항목(각 차원 d)과 크기 O(Q)의 ID 매핑만 전송한다.
6.3.3실험
구현. TGL[17]과 DGL[27]을 확장해 구현했고 PyTorch[28]가 하부 학습 프레임워크다. TGL의 병렬 시간적 샘플러(CSR 계열 표현으로 저지연 이웃 회수)를 채택하고, DGL이 배치마다 샘플된 동적 서브그래프와 필요 입력을 묶는 MFG를 구성한다. Supra는 NumPy[29]로 ID 중복 제거와 매핑 구축을 수행하고, 배치 간 파이프라인은 Python threading으로 실현한다.
| 데이터셋 | |V| | |E| | dv | de | α (평균 차수) | β (지름) | Θ (평균 갱신 거리) |
|---|---|---|---|---|---|---|---|
| LastFM[9] — 1개월 청취 이벤트 | 2 K | 1.3 M | 128 | 128 | 1306 | 1 | 2,873 |
| Wiki-Talk[30] — 사용자 간 상호작용 | 1.1 M | 7.8 M | 172 | 172 | 14 | 11 | 458,149 |
| Stack-Overflow[31] — 사용자 간 상호작용 | 2.6 M | 63.4 M | 172 | 172 | 49 | 13 | 1,354,646 |
| GDELT[17, 19] — 근 10억 규모 시간적 KG | 17 K | 191.3 M | 413 | 186 | 22,934 | 7 | 4,876,113 |
⟨Table 6.1⟩ 동적 그래프 통계. Θ는 전체 노드의 평균 갱신 거리로, 노드 v의 연속하는 두 갱신 사이에 발생하는 상호작용 수의 평균(θv)을 모든 노드에 대해 평균한 값이다. LastFM·Wiki-Talk·Stack-Overflow는 시간순 70%/15%/15% 분할, GDELT는 2019년 이전/2019년/2020년을 학습/검증/테스트로 사용한다.
백본과 베이스라인. 백본은 랜덤 푸리에 특징으로 시간을 인코딩하고 정적 GNN 유사 어텐션을 적용하는 TGAT[5], 노드 상태 벡터를 동적으로 유지하는 범용 프레임워크 TGN[6], 계산과 메시지 전파를 분리한 비동기 어텐션 모델 APAN[8]이다. 베이스라인 프레임워크는 TGL[17], Orca[16], Zebra[15]다. ETC와 TGL은 모델 불가지론적(model-agnostic) 프레임워크로 백본 기능을 보존하며 데이터 관리 최적화를 겨냥하는 반면, Orca·Zebra는 T-GNN 모델 설계 자체를 변경해 효율·효과를 높이되 동기식 T-GNN만 지원하고 고전적 TGN에 구현되어 있어 TGN 백본에서만 보고한다. 모든 프레임워크에서 입력 데이터는 학습 중 CPU 주메모리에 유지된다.
학습 설정. 태스크는 링크 예측이며 동수의 음성 링크를 샘플링해 테스트 AP로 평가한다. 이웃 샘플링은 top-k 최근 이웃(k = 10)이다. TGN·APAN의 기본 배치 크기는 네 데이터셋에서 각각 1000/1500/2000/2500이며, 공정성을 위해 전통 배칭을 먼저 실행해 그 배치들의 최대 정보 손실 점수를 임계 ε로 사용한다 — 두 배칭 전략이 동일한 손실 제약을 만족하게 된다. 이 설정에서 ETC의 분할 알고리즘은 평균 배치 크기 1180 / 2180 / 2938 / 2635를 산출한다. 노드 메모리 모듈이 없어 큰 배치에서 정보 손실을 겪지 않는 TGAT는 배치 크기를 5000으로 고정하고 분할 알고리즘을 적용하지 않는다. 각 모델을 5 에폭 학습하고 나머지 하이퍼파라미터는 TGL 기본값을 유지하며 추가 튜닝을 하지 않는다. 장비는 96 CPU 코어 · 256 GB 주메모리 · NVIDIA RTX 3090(24 GB) 1장이고, 각 실험을 3회 반복해 평균을 보고한다.
주요 결과 (Table 6.2)
| 데이터셋 | 백본 | TGL | ETC | Orca (TGN만) | Zebra (TGN만) |
|---|---|---|---|---|---|
| LastFM | TGN | 29.7 (2.1×) | 14.1 | 22.0 (1.6×) | 76.0 (5.4×) |
| TGAT | 8.5 (2.4×) | 3.6 | — | — | |
| APAN | 19.1 (1.8×) | 10.8 | — | — | |
| Wiki-Talk | TGN | 135.5 (2.3×) | 58.9 | 343.3 (5.8×) | 1029.5 (17.5×) |
| TGAT | 40.7 (2.0×) | 20.1 | — | — | |
| APAN | 160.4 (2.0×) | 81.8 | — | — | |
| Stack-Overflow | TGN | 1504.4 (3.1×) | 483.5 | 12428.7 (25.7×) | 30167.4 (62.4×) |
| TGAT | 339.4 (1.6×) | 215.9 | — | — | |
| APAN | 1696.3 (1.8×) | 937.4 | — | — | |
| GDELT | TGN | 4001.5 (3.3×) | 1222.4 | TLE | TLE |
| TGAT | 1338.2 (2.2×) | 619.9 | — | — | |
| APAN | 3302.9 (2.5×) | 1304.5 | — | — |
⟨Table 6.2 — 시간 부분⟩ 에폭당 실행시간(초), 괄호는 ETC 대비 배수. "TLE"는 한 에폭이 12시간 내에 완료되지 않음을 뜻한다. 원표는 각 행의 AP(%)도 함께 보고하며, ETC는 모든 T-GNN 백본에서 TGL과 동등한(일부 경우 소폭 상회하는) AP를 유지한다.
ETC의 효율. 기존 프레임워크 대비 1.6×~62.4×의 가속을 달성하고 대부분의 경우 2×를 넘는다. Zebra 대비 5.4×~62.4×인데, Zebra는 통상 데이터 접근 전략에 의존해 중복 전송 오버헤드를 크게 겪지만 ETC의 Supra가 이를 제거하기 때문이다. 중간 계산을 줄여 간접적으로 접근 비용을 완화하는 동적 캐싱의 Orca 대비로도 1.6×~25.7×인데, ETC가 더 직접적이고 효과적인 접근 최적화를 갖기 때문이다. 샘플링 면에서 가장 효율적인 베이스라인 TGL 대비로는 1.6×~3.3×다 — TGL의 병렬 샘플러가 이웃 샘플링 비용을 완화하지만 데이터 접근의 상당한 오버헤드를 간과하기 때문이다.
ETC의 효과성. 모든 백본에서 TGL과 동등한 정확도를 유지해 효율 개선이 효과성을 훼손하지 않음을 보인다. Orca·Zebra는 TGN에서 더 높은 정확도를 얻는 경우가 많은데, 이는 표현력·일반화 강화를 위해 TGN 모델 구조 자체를 수정했기 때문이며 ETC·TGL은 표준 TGN을 그대로 쓴다. 중요하게도 ETC의 최적화는 Orca·Zebra의 최적화와 직교한다 — 실제로 Orca로 강화한 TGN을 ETC 프레임워크 안에서 학습하면 예측 정확도가 유의미하게 개선된다(기술 보고서[34]).
ETC 분석 — TGL과의 직접 비교
모델 계산 1.3× · 분할 오버헤드 2.5%
배치 분할 알고리즘이 더 큰 배치를 가능하게 해 GPU 활용률과 계산 효율이 개선된다 — TGN·APAN에서 TGL 대비 평균 1.3× 빠른 모델 계산을 달성한다. 분할 알고리즘이 유발하는 오버헤드는 최소로, 엔드투엔드 학습 시간의 약 2.5%에 불과해 실용성이 확인된다.
데이터 준비 평균 3.3× · 최대 5.5×
Supra와 경량 파이프라인의 결합으로 데이터 준비 오버헤드가 크게 낮아진다 — 모든 설정에서 TGL보다 빠르고, 준비 시간을 최대 5.5× 절감하며 평균 3.3× 가속한다. 데이터 접근 시간만 보면 LastFM 4.9×(14.2→2.9 s), Wiki-Talk 4.2×(66.3→15.9 s), Stack-Overflow 3.9×(906.1→233.3 s), GDELT 6.1×(2599.6→427.5 s)다.
Supra는 더 조밀한 동적 그래프(LastFM, GDELT)에서 특히 효과적이다 — 조밀한 그래프가 이웃 샘플링에서 더 많은 중복 ID를 유발하므로 제거할 중복이 더 많기 때문이다.
단계별 비용과 파이프라인 효과
Supra 3단계의 시간 분해(초) — Step II(고유 입력의 CPU→GPU 전송)가 가장 비싸고(LastFM 2.9 / Wiki-Talk 15.9 / Stack-Overflow 233.3 / GDELT 427.5), Step I(고유 ID 식별과 역매핑 구축)도 상당한 오버헤드를 발생시키며(2.1 / 10.3 / 137.3 / 276.2), Step III(GPU에서 매핑으로 원 입력 재구성)는 추가 비용이 거의 없다(0.7 / 2.5 / 22.2 / 60.5).
배치 간 파이프라인은 추가로 1.2×~1.6× 가속을 제공한다 — LastFM 16.9→14.1, Wiki-Talk 75.7→58.9, Stack-Overflow 783.6→483.5, GDELT 1850.0→1222.4 s. CPU 준비와 GPU 계산의 중첩이 오버헤드를 더 줄인다.
배치 간 동적 데이터 배치
CROSS-BATCH DYNAMIC DATA PLACEMENT
SIMPLE6.4.1개요
SIMPLE은 GPU 버퍼를 갖춘 최초의 범용 T-GNN 학습 시스템이다. CPU–GPU에 걸친 동적 하이브리드 데이터 배치를 채택해, 간선 특징 같은 메모리 집약적 입력은 CPU 주메모리에 두고, 동적으로 변하는 핫 데이터를 수용하는 유연한 GPU 버퍼를 유지한다.
6.4.2전처리
전처리는 CPU에서 샘플러와 계획 생성기(plan generator)로 수행된다. 먼저 입력 동적 그래프에 사전 샘플링(pre-sampling)을 수행해 학습 중 예상되는 데이터 접근 패턴을 분석한다 — 각 배치에서 대상 상호작용(간선)에 관여한 모든 루트 노드에 대해 연관 타임스탬프에 기반한 시간적 이웃 샘플링을 실행한다. 효율을 위해 TGL[17]의 병렬 C++ 샘플러를 통합하고 기본적으로 top-k 최근 이웃 전략[6, 16, 17]을 채택한다. 샘플러는 모든 배치에 필요한 입력 데이터 ID를 출력하고, 계획 생성기가 이 ID들에서 접근 패턴을 추출해 배치별 GPU 버퍼 계획을 산출한다 — 각 계획은 해당 배치에서 GPU 메모리에 유지되어야 할 입력 데이터 ID 집합을 명시한다.
6.4.3학습 워크플로
ALGORITHM 2 — SIMPLE의 단일 에폭 T-GNN 학습
Input: 학습 배치 수 N; CPU 측 전체 입력 데이터 H; 배치별 필요 ID 리스트 D=[d⁽¹⁾,…,d⁽ᴺ⁾];배치별 버퍼 계획 P=[p⁽¹⁾,…,p⁽ᴺ⁾]; GPU 버퍼 ξ⁽⁰⁾; 미학습 T-GNN 모델 θ⁽⁰⁾
Output: 학습된 T-GNN 모델 θ⁽ᴺ⁾
1 for i ← 1 : N do
2 H⁽ⁱ⁾ ← LOAD(d⁽ⁱ⁾, ξ⁽ⁱ⁾, H) ▷ CPU–GPU 데이터 적재 (Loader)
3 ξ⁽ⁱ⁺¹⁾ ← UPDATE(p⁽ⁱ⁾, ξ⁽ⁱ⁾, H⁽ⁱ⁾) ▷ GPU 버퍼 갱신 (Updater)
4 θ⁽ⁱ⁾ ← TRAIN(θ⁽ⁱ⁻¹⁾, H⁽ⁱ⁾) ▷ 모델 계산 (Trainer)
5 end for
시간적 이웃 샘플링은 학습 중 수행되지 않는다 — 모든 배치의 필요 ID가 전처리에서 이미 사전 계산되었다.
Loader
배치 B(i)의 필요 ID d(i)가 주어지면 CPU 주메모리(H) 또는 GPU 버퍼(ξ)에서 데이터를 회수한다. 정적 GNN 시스템의 로더 설계[20–22]를 따르되 메타데이터용 GPU 공간을 추가 할당한다 — 이 해시 테이블이 특정 데이터의 버퍼 상주 여부와 정확한 위치를 빠르게 조회하게 하며, 조회 오버헤드는 통상 전체 학습 시간의 1~2%다.
시간 복잡도는 O(U(i))로 U(i)는 CPU에서 가져와야 하는 데이터 수다. GPU 버퍼 덕에 상당 부분을 GPU에서 직접 접근해 U(i) ≪ |d(i)|가 되어 적재 비용이 크게 줄고, 버퍼 관리로 적재 오버헤드를 80% 이상 절감한다.
Updater
적재된 H(i)를 받아 GPU 버퍼의 본체(저장 데이터)와 메타데이터를 유지·갱신한다. 버퍼 계획 p(i), 새로 적재된 H(i), 현재 버퍼 ξ(i)의 세 입력이 갱신을 안내한다. 모든 계획이 전처리에서 사전 생성되므로 갱신자는 CPU 메모리에서 해당 계획을 곧바로 가져와 데이터를 효율적으로 추적·교체한다.
LRU[25] 같은 런타임 정책과 달리 계획을 사전 생성하는 것은 반복적 미세 조정이 잦은 T-GNN 학습에 유리하다 — 정적 계획은 학습 실행 간 재사용되어 반복 오버헤드를 줄인다. 갱신 전 과정을 GPU에서 실행해 불필요한 전송을 피하며, 복잡도는 O(Z(i))(Z(i) = |d(i)| + |p(i)|)로 평균 전체 학습 시간의 10% 미만이다.
Trainer
버퍼 갱신이 끝나면 이미 적재된 H(i)로 모델 계산을 진행한다. SIMPLE은 최신 T-GNN 모델[5, 6, 16]의 즉시 사용 가능한 구현을 포함하며, 자체 모델을 학습하려는 사용자는 커스텀 모델 로직만 제공하면 전처리·데이터 적재·버퍼 관리는 자동 처리된다.
전형적 T-GNN은 재귀적 시간적 집계를 수행하며 배치 B(i)의 시간 복잡도는 O(V(i) · ηL)다 — V(i)는 (타임스탬프를 가진) 대상 노드 수, η는 샘플링 fanout, L은 메시지 패싱 레이어 수다.
※ 표준 워크플로[17]와 비교한 SIMPLE의 두 전처리 강화는 (1) 이웃 샘플링 결과의 물질화(materializing)와 (2) GPU 버퍼 계획의 사전 생성이며, 학습 중에는 효율적 GPU 버퍼 기반 적재 메커니즘과 경량 버퍼 갱신 단계로 차별화된다.
6.4.4동적 데이터 배치 — 구간 선택 문제
⟨Fig 6.11⟩ 사전 샘플링으로 수집한 전역 출현 패턴에서 후보 배치 구간을 추출하고, 시간 순이익 f(σ)로 그리디 선택을 안내한다. 패턴은 어떤 데이터가 등장하는지뿐 아니라 몇 번 등장하는지까지 반영해 배치 내 중복까지 활용한다.
n개 후보 배치 구간 {σ(1), …, σ(n)}(각 크기 si, 이익 pi)이 주어졌을 때, GPU 버퍼 제약을 만족하며 총 이익을 최대화하는 부분집합을 선택한다. T를 총 타임스팬(배치 간 간격) 수, k를 가용 GPU 버퍼 크기라 하면:
max Σi=1n pixi s.t. (6.10) Σi=1n sitxi ≤ k, ∀t = 1, …, T · (6.11) sit ∈ {0, si} · (6.12) xi ∈ {0, 1}
sit는 i번째 구간이 t번째 타임스팬을 점유하는지를 나타낸다(점유 시 si, 아니면 0). Hardness — T = 1(학습이 두 배치만 포함)일 때 고전적 0-1 배낭 문제[35–37]가 ISPT의 특수 사례이므로 ISPT는 NP-hard다.
2단계 구간 선택. 1단계에서 서로 다른 구간 범주에 버퍼 예산을 배분하고, 2단계에서 각 범주 안에서 그리디로 ISPT를 독립적으로 푼다. 계획 생성기는 노드 관련 데이터(갱신 가능한 노드 상태 벡터 + 정적 노드 특징)와 간선 관련 데이터(정적 간선 특징)에 각각 예산을 배분한다(Eq 6.13). 이후 크기 예산 k(·)를 타임스팬당 허용 중첩 구간 개수 제약으로 변환한다 — k(·) = k(·) / h(·) (Eq 6.14, h(·)는 해당 입력의 메모리 크기). 즉 원래의 크기 제약이 동일 유형 구간이 임의 타임스팬에서 k(·)개를 넘어 중첩할 수 없다는 개수 기반 제약으로 재정식화된다.
ALGORITHM 3 — ONE-PASS INTERVAL SELECTION
Input: 구간 리스트 L=[σ(1),…,σ(n)]; 시간 순이익 F=[f(σ(1)),…]; 개수 예산 k⁽·⁾; 타임스팬 수 TOutput: 선택 구간 리스트 L̃
1 빈 리스트 초기화 L̃ ← [ ]
2 예산 벡터 b ← [k⁽·⁾, …, k⁽·⁾], b ∈ ℕᵀ
3 F의 내림차순으로 L을 정렬 → L̂ ▷ O(n log n)
4 for σ(·) in L̂ do
5 s ← σ(·)[0], e ← σ(·)[1]
6 부분벡터 추출 r ← b[s : e+1]
7 for j ∈ {0,…,e−s} do r[j] ← r[j] − 1 end for
10 if r[j] ≥ 0 for all j then ▷ 예산 위반 없음
11 b[s : e+1] ← r
12 L̃에 σ(·) 추가
13 end if
14 end for
시간 복잡도 O(n · m), m은 실제 평균 구간 길이(m < T). 제약이 GPU 메모리 사용이 타임스팬별 예산을 넘지 않게 보장해 오버플로를 방지한다.
ALGORITHM 4 — BUFFER PLAN CONSTRUCTION (ZigZag)
Input: 선택 구간 리스트 L̃=[σ(1),…,σ(n)]; 배치 수 B / Output: 버퍼 갱신 계획 리스트 P1 전방 포인터 q ← 0
2 활성 인덱스 리스트 D ← [ ]
3 출력 계획 리스트 P ← [ ]
4 L̃을 s(·) 오름차순으로 정렬
5 for i = 1 to B do
6 D̂ ← [ ]
7 while L̃[q][0] ≤ i do ▷ 전방 스캔
8 q ← q + 1; D̂에 q 추가
10 end while
11 for d in D do ▷ 후방 스캔
12 if L̃[d][1] > i then D̂에 d 추가
14 end if end for
16 ID_list ← Extract_ID(D̂, L̃)
17 P에 ID_list 추가
18 D ← Update(D̂, i)
19 end for
시간 복잡도 O(B · l), l은 배치당 평균 적격 구간 수(l ≪ n). 소박한 전수 검사는 O(B · n)으로 학습 시간을 초과할 수도 있다.
버퍼 계획 구성의 조건과 ZigZag의 착안. 배치 Bi의 계획 Pi는 s(σ) ≤ i(Eq 6.23)와 e(σ) > i(Eq 6.24)를 만족하는 모든 구간의 입력 ID를 포함한다. 결정적 시간 관계는 연속하는 두 배치의 적격 구간이 대부분 공유된다는 것이다 — s(σ) < i이고 e(σ) > i인 구간(배치 i를 걸치는 구간)은 배치 i−1에서도 유효했음이 틀림없다. 이 중첩을 활용해 전방 스캔(배치 i에서 새로 적격이 된 구간 추가)과 후방 스캔(이전 적격 구간 중 여전히 유효한 것 유지)으로 계획을 증분 생성한다.
Lemma 3(균일 크기 ISPT). 단일 유형 d 구간에 대해 개수 예산과 그 상한을 Kd, Kd*라 하면 ΘdOPT(Kd) ≥ vol(d) · Kd / (2Kd*) (Eq 6.16)이 성립한다(vol(d) = ΘdOPT(Kd*), 유형 d 구간 이익 총합의 최대). 증명 요지 — 귀류법으로, Kd(j)/Kd(i) = c ∈ ℕ⁺에서 가정이 성립하면 ΘOPT(Kd(j))를 더 작은 예산의 실현 가능해들로 분해하고 비둘기집 원리를 적용해 Θx(Kd(i)) > ΘOPT(Kd(i))인 해의 존재를 얻어 모순에 이른다.
Theorem 2(두 유형의 일반 사례 — T-GNN 학습 설정). 크기 예산을 K라 할 때 SIMPLE의 해 ALG와 최적해 OPT에 대해
ΘALG(K) / ΘOPT(K) ≥ K / (4MT) (Eq 6.19)
가 성립한다. M은 모든 구간 크기의 합(T-GNN 학습 입력 데이터의 총 메모리 풋프린트), T는 총 타임스팬이다. 증명 요지 — Lemma 3, Theorem 1, Eq 6.13의 예산 배분 원리, 그리고 ΘOPT(K) ≤ vol(V) + vol(E)를 결합해 Eq 6.20 → 6.21 → 6.22의 연쇄 부등식으로 K(vol(V)² + vol(E)²) / (2MT(vol(V) + vol(E))²) ≥ K/(4MT)를 얻는다.
6.4.6실험
설정. 데이터셋은 ETC와 동일한 4종(Table 6.6은 최대 간선 타임스탬프 max(t)를 추가 보고 — LastFM 1.3e8, Wiki-Talk 2.0e8, Stack-Overflow 2.4e8, GDELT 1.8e5). 베이스라인은 TGL[17]이며(DGL은 T-GNN 학습을 기본 지원하지 않아 제외), 백본은 TGAT·TGN·Orca 세 가지다. 공정 비교를 위해 top-k(k=10) 최근 이웃 샘플링과 표준 2-레이어 메시지 패싱을 양쪽에 정렬하고, 배치 크기는 LastFM·Wiki-Talk 2000, Stack-Overflow·GDELT 4000이다. GPU 버퍼 크기는 전체 입력 메모리 풋프린트에 대한 사용자 설정 비율로 정의하며 주 실험에서 기본값 0.1이다. 검증 성능이 3 에폭 연속 개선되지 않으면 학습을 종료한다. 장비는 RTX 3090(24 GB) 1장 · Xeon Gold 5220R 96코어 · 256 GB 주메모리이며 3회 독립 실행의 평균을 보고한다. 정확도는 직접 비교하지 않는다 — 양 시스템 모두 범용 프레임워크로서 모델 효과성에 영향을 주는 추가 구성요소를 도입하지 않으므로, 평가의 초점은 학습 효율과 시스템 설계다.
1.8–3.8× 가속 · 적재 80.5–96.5% 절감
모든 평가 설정에서 TGL 대비 1.8×~3.8×의 가속을 달성하며 12개 사례 중 11개에서 2× 초과다. 주된 기여 요인은 CPU–GPU 데이터 적재 오버헤드의 실질적 감소로, 동적 데이터 배치로 이를 80.5%~96.5% 줄인다.
적재 비용의 정도는 모델마다 다르다 — 최대 데이터셋 GDELT에서 Orca의 적재 오버헤드는 TGN의 약 1/3인데, Orca가 중간 임베딩 재사용으로 시간적 계산 그래프를 암묵적으로 가지치기해 중복 입력 페치를 피하기 때문이다. 그런 최적화 아래에서도 SIMPLE은 Orca의 적재 비용을 추가로 80.5%~94.8% 줄이고 대부분 2× 이상의 학습 가속을 일관되게 달성한다.
전처리 6.6% · ZigZag 최대 306×
전처리는 경량으로 평균 엔드투엔드 학습 시간의 6.6%만 소비하며, 이는 대부분 ZigZag 덕이다. ZigZag는 버퍼 계획 생성을 최대 두 자릿수 배 가속한다 — LastFM에서는 1.06~1.24×에 그치지만, Wiki-Talk 9.69~17.44×, Stack-Overflow 18.48~41.63×, GDELT는 193.61~306.57×(예: TGAT 10772.73 s → 35.14 s)에 이른다. 구간 탐색 공간의 대폭 축소에서 오는 가속이다.
GPU 버퍼 조회 비용은 무시할 만하고(전체 학습 시간의 약 1.0~2.5%), 갱신도 경량으로 설정에 따라 2.0%~23.0%를 차지한다 — Loader·Updater 모듈의 효과성을 보여준다.
| 데이터셋 | 버퍼 예산 비율 | 데이터 적재 (s) | 학습 (s, 전처리 제외) |
|---|---|---|---|
| Wiki-Talk · TGN | 0% | 289.3 | 462.2 |
| 1% | 40.8 | 168.1 (2.8×) | |
| 5% | 28.0 | 153.7 | |
| 10% (기본값) | 25.0 | 151.7 | |
| 20% | 20.2 | 146.2 | |
| Stack-Overflow · TGN | 0% | 3571.5 | 5291.2 |
| 1% | 470.4 | 1676.1 (3.2×) | |
| 5% | 290.3 | 1586.8 | |
| 10% (기본값) | 113.8 | 1438.2 | |
| 20% | 112.4 | 1408.7 |
⟨Table 6.9⟩ 버퍼 예산 비율의 효과(에폭당 시간, 초). 비율이 커지면 적재·학습 시간이 모두 감소하지만, 최소 1%만으로도 최대 3.2× 가속이 관찰되고 이후 한계 이득이 체감한다 — SIMPLE의 전략적 동적 배치가 효과적임을 보여준다. 실무에서는 GPU 메모리의 1~10% 할당만으로 이미 유의미한 적재 비용 절감을 얻는다.
| 데이터셋 (TGN, 버퍼 비율 0.1) | 배치 전략 | 데이터 적재 (s) | 학습 (s) |
|---|---|---|---|
| Wiki-Talk | Static (최신 정적 배치) | 58.4 | 184.1 |
| LRU[25] | 43.3 | 287.2 | |
| SIMPLE | 25.0 | 151.7 | |
| Stack-Overflow | Static | 1726.9 | 3319.6 |
| LRU[25] | 540.9 | 2614.3 | |
| SIMPLE | 113.8 | 1438.2 |
⟨Table 6.10⟩ 데이터 배치 전략의 효과(에폭당 시간, 초). LRU는 적재 효율 면에서 정적 전략을 앞서 동적 버퍼 관리의 이점을 뒷받침하지만, 최근 사용만에 기반한 반응적·배치별 의사결정 탓에 Wiki-Talk에서는 전체 학습 비용이 정적 전략보다 오히려 높다. 또한 LRU의 적재 절감은 SIMPLE보다 작고 그 격차는 더 큰 Stack-Overflow에서 벌어진다 — LRU가 제한된 과거 접근 패턴에만 의존하는 반면 SIMPLE은 전역 출현 통계로 계획을 생성하기 때문이다.
결론
CONCLUSION
기존 T-GNN 학습 파이프라인은 부적합한 배칭과 높은 입력 데이터 적재 비용 탓에 확장성 문제를 겪는다. 이 두 문제를 다루기 위해 먼저 ETC를 제안했다 — 정보 손실의 영향을 효과적으로 완화하면서 큰 배치 크기를 지원해 모델 계산 효율을 높이는 새로운 배칭 전략, 시간적 이웃 회수에 맞춘 3단계 데이터 접근 정책으로 입력 접근 오버헤드를 크게 줄이는 설계, 그리고 데이터 접근과 모델 계산을 분리하는 경량 파이프라인을 갖춘다. 광범위한 실험은 다양한 모델과 대규모 데이터셋에서 최신 프레임워크 대비 1.6×~62.4×의 학습 가속을 입증한다.
이어 SIMPLE을 도입했다 — 과도한 CPU–GPU 데이터 적재를, 학습 중 전송 오버헤드를 유의미하게 줄이는 동적 데이터 배치 전략으로 해결하는 범용 시스템이다. 실증 평가는 데이터 적재 비용을 80.5~96.8% 낮추고 최신 시스템 TGL 대비 평균 2.6× 학습 가속을 제공함을 보인다. 향후에는 산업 규모 동적 그래프 학습의 확장성 요구에 대응하기 위해 SIMPLE을 분산 학습으로 확장하는 것이 유망하다.
※ 원문은 §6.4.6 실험 서술에서 적재 절감 폭을 80.5~96.5%로, 결론에서 80.5~96.8%로 기술한다. 여기서는 각각 원문 표기를 그대로 옮겼다.
참고문헌
CHAPTER 6 · 38 REFERENCES
- [1] Perozzi et al. 2014. DeepWalk: Online learning of social representations. KDD.
- [2] Grover & Leskovec. 2016. node2vec: Scalable feature learning for networks. KDD.
- [3] Hamilton et al. 2017a. Inductive representation learning on large graphs (GraphSAGE). NeurIPS 30.
- [4] Zeng et al. 2020. GraphSAINT: Graph sampling based inductive learning method. ICLR.
- [5] Xu et al. 2020. Inductive representation learning on temporal graphs (TGAT). ICLR.
- [6] Rossi et al. 2020. Temporal Graph Networks for Deep Learning on Dynamic Graphs (TGN). ICML GRL Workshop.
- [7] Wang et al. 2021. Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks (CAW). ICLR.
- [8] Wang et al. 2021. APAN: Asynchronous propagation attention network for real-time temporal graph embedding. SIGMOD.
- [9] Kumar et al. 2019. Predicting dynamic embedding trajectory in temporal interaction networks (JODIE, LastFM). SIGKDD.
- [10] Kipf & Welling. 2017a. Semi-Supervised Classification with Graph Convolutional Networks. ICLR.
- [11] Velickovic et al. 2018. Graph Attention Networks (GAT). ICLR.
- [12] Goyal et al. 2020. dyngraph2vec: Capturing network dynamics using dynamic graph representation learning. Knowledge-Based Systems 187.
- [13] Hajiramezanali et al. 2019. Variational graph recurrent neural networks. NeurIPS.
- [14] Pareja et al. 2020. EvolveGCN: Evolving graph convolutional networks for dynamic graphs. AAAI.
- [15] Li et al. 2023b. Zebra: When Temporal GNNs Meet Temporal Personalized PageRank. VLDB 16(6).
- [16] Li et al. 2023a. Orca: Scalable Temporal GNN Training with Theoretical Guarantees. PACMMOD 1(1).
- [17] Zhou et al. 2022. TGL: A General Framework for Temporal GNN Training on Billion-Scale Graphs. PVLDB.
- [18] Trivedi et al. 2019. DyRep: Learning representations over dynamic graphs. ICLR.
- [19] Leetaru & Schrodt. 2013. GDELT: Global data on events, location, and tone, 1979–2012. ISA Annual Convention.
- [20] Lin et al. 2020a. PaGraph: Scaling GNN training on large graphs via computation-aware caching. SoCC.
- [21] Yang et al. 2022a. GNNLab: a factored system for sample-based GNN training over GPUs. EuroSys.
- [22] Zhang et al. 2023a. DUCATI: A Dual-Cache Training System for GNNs on Giant Graphs with the GPU. PACMMOD 1(2).
- [23] Zhu et al. 2019. AliGraph: A Comprehensive Graph Neural Network Platform (in-degree 기준). PVLDB 12(12).
- [24] Min et al. 2022. Graph neural network training and data tiering (PageRank 기준). KDD.
- [25] O'Neil et al. 1993. The LRU-K page replacement algorithm for database disk buffering. SIGMOD.
- [26] Korte & Vygen. 2008. Combinatorial optimization: Theory and algorithms (빈 패킹). Springer.
- [27] Wang et al. 2019a. Deep Graph Library. arXiv:1909.01315.
- [28] Paszke et al. 2019. PyTorch: An imperative style, high-performance deep learning library. NeurIPS.
- [29] Harris et al. 2020. Array programming with NumPy. Nature 585.
- [30] Wiki-Talk dataset. SNAP (snap.stanford.edu/data/wiki-talk-temporal.html).
- [31] Stack-Overflow dataset. SNAP (snap.stanford.edu/data/sx-stackoverflow.html).
- [32] Jin et al. 2022. Neural temporal walks: Motif-aware representation learning on continuous-time dynamic graphs. NeurIPS.
- [33] Cong et al. 2023. Do we really need complicated model architectures for temporal networks? ICLR.
- [34] ETC 기술 보고서. github.com/eddiegaoo/ETC/blob/main/Technical-report.pdf
- [35] Martello & Toth. 1990. Knapsack problems: algorithms and computer implementations. Wiley.
- [36] Fréville. 2004. The multidimensional 0–1 knapsack problem: An overview. EJOR 155(1).
- [37] Cacchiani et al. 2022. Knapsack problems — an overview of recent advances. Part II. Computers & Operations Research 143.
- [38] Li et al. 2021. AI meets database: AI4DB and DB4AI (데이터 증강). SIGMOD.