기술 요약: RankGraph-2

문제 정의

추천 시스템을 위한 십억 단위 노드 규모의 그래프 기반 검색(retrieval)을 배포하려면 그래프 구축(graph construction), 표현 학습(representation learning), 그리고 **실시간 서빙(real-time serving)**이라는 세 가지 밀접하게 결합된 문제를 해결해야 합니다. 기존 연구들은 대개 이러한 단계들을 개별적으로 다룹니다. 학술 연구는 종종 소규모 정적 그래프에서 모델 아키텍처를 최적화하는 데 집중하며, 산업계 시스템은 훈련 인프라는 발전시키지만 입력 그래프가 주어져 있다고 가정하고 서빙 비용은 무시하는 경향이 있습니다. 이러한 분절된 접근 방식은 다음과 같은 병목 현상을 초과합니다:

• 구축(Construction): 십억 노드 시스템에 대해 전체 공동 참여(co-engagement) 그래프를 나이브하게 구축하면 수백 조 개의 엣지가 생성되어 저장 및 처리가 불가능해집니다.
• 훈련(Training): 이러한 거대 그래프에서 훈련하려면 실시간으로 이웃을 추출하기 위해 고가의 온라인 그래프 인프라(예: 분산 샘플링 엔진)가 필요합니다.
• 서빙(Serving): 동적인 사용자 풀(예: 최근 15분간 활성 사용자)에 대해 온라인 근사 최근접 이웃(KNN) 검색을 통해 임베딩을 서빙하려면 수천 대의 머신이 필요하며, 이는 과도한 지연 시간과 비용을 발생시킵니다.

본 논문은 한 단계만을 최적화하고 다른 단계의 제약 조건을 고려하지 않는 것은 차선의 결과를 초래한다고 주장합니다. 핵심 과제는 그래프의 노드가 수십 억 개이고 잠재적 엣지가 수백 조 개인 상황에서 구축, 훈련, 서빙을 어떻게 공동 설계(co-design)할 것인가 하는 점입니다.

방법론: 라이프사이클 공동 설계 (Lifecycle Co-Design)

RankGraph-2는 유사도 기반 검색(User-to-User-to-Item [U2U2I] 및 User-to-Item-to-Item [U2I2I])을 위해 세 가지 라이프사이클 단계를 통합하여 공동 설계한 프레임워크입니다. 이 시스템은 다운스트림 단계(서빙, 훈련)의 요구사항이 업스트림 단계(구축)를 형성해야 한다는 원칙에 따라 작동합니다.

1. 그래프 구축 (Upstream)

훈련(자기 완결적 데이터)과 서빙(시간 단위의 신선도)의 요구사항을 충족하기 위해 구축 파이프라인은 다음을 수행합니다:

• 이종 그래프 스키마 (Heterogeneous Graph Schema): 참여 데이터(클릭, 좋아요, 공유, 구매)로부터 유도된 세 가지 엣지 유형인 User-Item (U-I), User-User (U-U), Item-Item (I-I)을 가진 그래프를 구축합니다.
• 인기 편향 보정 (Popularity Bias Correction): 인기 있는 아이템이 표현을 지배하는 것을 방지하기 위해 I-I 엣지 가중치를 조정합니다. 가중치는 타겟 아이템의 인기에 반비례하는 인자로 스케일링되어, 롱테일 아이템이 소외되지 않도록 합니다.
• 엣지 서브샘플링 (Edge Subsampling): 수백 조 개의 엣지를 수천 억 개의 엣지로 줄입니다. 여기에는 U-U 엣지를 위한 고가치 노드 유지와 각 노드에 대한 상위 가중치 엣지($K_{CAP}$) 유지가 포함됩니다.
• 사전 계산된 이웃 (Pre-computed Neighborhoods): 온라인 샘플링 대신, 시스템은 "백본(backbone)" 그래프에서 개인화된 페이지랭크(PPR)를 사용하여 각 노드의 가장 중요한 멀티홉 이웃 $K_{IMP}$를 사전 계산합니다. 동일 유형의 이웃이 부족한 노드의 경우, 이전 임베딩에 대한 KNN을 폴백(fallback) 메커니즘으로 사용합니다.
• 출력: 파이프라인은 엣지, 노드 특징, 사전 계산된 이웃을 포함하는 "엣지 중심(edge-centric)" 데이터를 생성하며, 이는 온라인 그래프 저장소 없이 직접 인입될 준비가 된 상태입니다. 전체 파이프라인은 1시간 이내에 완료되어 3시간의 리프레시 주기를 가능하게 합니다.

2. 모델 훈련 (Midstream)

훈련 단계는 사전 계산된 자기 완결적 데이터를 인입하여 온라인 그래프 인프라(그래프 저장소 또는 분산 샘플링 엔진 없음)의 필요성을 제거합니다.

• 아키텍처: 사용자 및 아이템을 위한 멀티 헤드 인코더를 갖춘 단순한 이종 어그리게이터(heterogeneous aggregator)를 사용합니다. 이는 보지 못한 노드에도 일반화됩니다(귀납적 설정).
• 목적 함수: 마진 랭킹 손실(margin ranking loss)과 대비 학습(contrastive link prediction)을 위한 InfoNCE 손실을 결합합니다.
• 공동 학습 (Co-Learning): 결정적으로, 훈련 과정은 임베딩과 함께 클러스터 인덱스를 공동 학습합니다. 모델은 임베딩 품질뿐만 아니라 잔차 양자화(residual quantization) 목적 함수를 통한 재구성된 임베딩의 품질까지 최적화합니다.
• 정규화 (Regularization): 지속적인 훈련 중에 발생하는 "코드북 붕괴(codebook collapse, 일부 코드가 과도하게 사용되는 현상)"를 방지하기 위해 시스템은 다음을 채택합니다:
  • 정규화 손실: 과거 배치들의 경험적 분포를 기반으로 자주 사용되는 코드를 강화하는 현재 배치를 페널티화합니다.
  • 편향된 코드 선택: 탐색 메커니즘으로서 사용 빈도가 낮은 엔트리를 선호하는 코드를 선택합니다.

3. 실시간 서빙 (Downstream)

서빙 전략은 공동 학습된 인덱스를 활용하여 값비싼 온라인 KNN을 클러스터 기반 접근 방식으로 대체합니다.

• 클러스터 할당: 각 사용자는 잔차 양자화를 통해 계층적 클러스터 코드를 할당받습니다.
• U2U2I 검색: 유사한 사용자를 검색하는 대신, 시스템은 대상 사용자의 할당된 클러스터의 **클러스터 큐(cluster queue)**에서 최신 아이템을 읽습니다. 이 큐는 해당 클러스터의 최근 활성 멤버들에 의해 유지됩니다.
• 효율성: 이를 통해 U2U2I 검색을 단순한 룩업(lookup)으로 축소하여, 동적인 사용자 풀에 대한 온라인 KNN의 필요성을 제거합니다.

주요 기여

1. 라이프사이클 공동 설계 프레임워크: 서빙, 훈련, 구축의 요구사항이 각 단계로 전파되어 독립적인 최적화로는 달성할 수 없는 성능을 끌어내는 프레임워크를 식별하고 구현했습니다.
2. 그래프 인프라가 필요 없는 훈련 (Graph-Infra-Free Training): 유사도 기반 검색이 온라인 그래프 인프라를 필요로 하지 않음을 입증했습니다. 사전 계산된 이웃(PPR 활용)은 온라인 샘플링과 대등한 품질을 제공하여, 표준 ML 인프라에서도 훈련이 가능하게 합니다.
3. 이종 그래프 구축: 세 가지 엣지 유형(U-U, I-I, U-I)을 가지며, 인기 편향 보정과 PPR 기반 이웃 사전 계산을 특징으로 하는 참여 데이터 기반의 그래프를 제안합니다.
4. 공동 학습된 클러스터 인덱스: 코드북 붕괴를 방지하기 위해 새로운 정규화 및 편향된 코드 선택을 사용하는 잔차 양자화 인덱스를 개발하여 서빙 비용을 83% 절감했습니다.
5. 성능 향상: 공동 설계된 단순한 아키텍처가 복잡한 베이스라인(GAT + Deep Graph Infomax 및 PyTorch-BigGraph)보다 리콜(recall) 및 온라인 지표에서 크게 우수함을 보여줍니다.

결과

이 시스템은 Meta의 여러 서비스에 배포되어 수십 억 명의 사용자에게 서비스되었습니다.

• 오프라인 리콜 (Offline Recall):
  • 사용자 임베딩: RankGraph-2는 (더 복잡한 아키텍처를 사용하지만 더 단순한 이분 그래프를 사용하는) GAT + Deep Graph Infomax 모델보다 3.8배 높은 Recall@5를 달성했습니다.
  • 아이템 임베딩: 아이템 검색에서 PyTorch-BigGraph보다 2.1배 높은 Recall@100을 달了했습니다.
• 온라인 A/B 테스트 (14일):
  • U2I2I 검색에서 최대 +0.96% CTR 및 +2.75% CVR을 기록했습니다.
  • U2U2I 검색에서도 일관된 개선을 보여주었습니다.
• 인프라 비용:
  • 온라인 KNN을 공동 학습된 클러스터 인덱스로 교체함으로써 U2U 서빙 인프라 비용을 83% 절감했습니다.
• 배포: 20개 이상의 주요 Meta 서비스 런칭에 적용되었습니다.

의의 및 주장

본 논문은 성능의 주요 동력이 모델의 복잡성이 아니라 라이프사이클 공동 설계라고 주장합니다. 이웃 계산을 오프라인으로 이동함으로써, 시스템은 지연 시간 및 인프라 제약으로 인해 온라인 환경에서는 불가능한 작업(멀티홉 PPR, 인기 편향 보정, 이종 엣지 구축)을 가능하게 합니다.

저자들은 유사도 기반 검색을 위해 복잡한 GNN을 지원하려고 온라인 그래프 인프라에 투자하는 기존 방식이 잘못된 트레이드오프일 수 있다고 주장합니다. 대신, 표준 ML 인프라 상에서 고품질의 오프라인 그래프 구축에 투자하는 것이 더 우수한 검색 품질과 더 낮은 운영 비용을 모두 달성할 수 있는 길이라고 제안합니다. 본 논문은 RankGraph-2를 생성형 파운데이션 모델의 경쟁자가 아니라, 글로벌 협업 구조를 포착하는 보완적인 구조적 사전 지식(structural prior)으로 위치시키며, 이는 하위 랭킹을 위한 시계열 의도 모델과 결합될 수 있습니다.