기술 요약: 그래프 코서닝(Graph Coarsening) 및 레이블 전파를 통한 효율적인 추천

문제 정의

그래프 기반 추천 시스템은 통신 분야와 같이 복잡한 사용자-아이템 및 사용자-사용자 상호작용을 모델링하기 위해 산업 현장에서 널리 사용됩니다. 그러나 이러한 데이터셋이 수백만 또는 수십억 개의 노드와 엣지로 확장됨에 따라, 심각한 확장성 및 효율성 문제에 직면하게 됩니다. 표준 그래프 신경망(GNN)은 강력하지만, 막대한 계산 자원을 요구하고, 오버 스무딩(over-smoothing) 문제를 겪으며, 거대 그래프에서의 장거리 의존성 처리에 어려움을 겪습니다. 반대로, 레이블 전파 알고리즘(LPA)과 같은 경량 대안은 계산 효율성은 높지만, 모든 엣지를 반복적으로 순회해야 하므로 대규모 산업용 그래프에 직접 적용할 경우 처리 속도가 매우 느려집니다. 또한, 단순한 그래프 다운샘플링은 중요한 커뮤니티 구조를 파괴하거나 허브(hub) 노드를 고립시켜 추천 품질을 저하시키는 경우가 많습니다. 핵심 과제는 예측 품질과 계산 비용 사이의 균형을 맞추는 것이며, 특히 추천이 개인이 아닌 암묵적 사용자 그룹(예: 가족)에 맞춰져야 하는 도메인에서 이 문제가 두드러집니다.

방법론

저자들은 **비즈니스 주도형 그래프 코서닝(Business-driven graph coarsening)**과 **다단계 레이블 전파(Multi-step label propagation)**를 결합한 유연한 2단계 확산 프레임워크를 제안합니다. 이 프레임워크는 무방향 사용자 그래프 $G=(V, E, Y)$를 대상으로 하며, 세 가지 뚜렷한 단계로 진행됩니다.

1. 그래프 코서닝 (비즈니스 주도형 집계)

일반적인 커뮤니티 탐지 알고리즘을 사용하는 대신, 이 방법은 통신 분야와 관련된 특정 도메인 휴리스틱을 기반으로 사용자를 "슈퍼 노드(super nodes, 커뮤니티)"로 집계합니다. 사용자는 다음과 같은 조건을 충족할 때 병합됩니다:

• 상호작용 빈도: 높은 통화 시간 또는 통화 빈도.
• 성씨(Surname): 동일한 성씨 공유.
• 케어(Caring): 한 사용자가 다른 사용자를 위해 고객 지원을 자주 요청하는 경우.
• 잔액(Balance): 재정적 의존성 (예: 타인의 잔액 충전).
• 중복성(Redundancy): 단일 사용자와 연결된 다수의 회선.

이 과정은 슈퍼 노드가 암묵적 가족 또는 가구를 나타내는 코서닝된 그래프 $G'$를 생성합니다. 새로운 레이블 행렬 $Y'$는 커뮤니티 내 모든 사용자가 수락한 오퍼(offers)를 집계하여 구축됩니다.

2. 커뮤니티 간 전파 (Inter-Community Propagation)

코서닝된 그래프 $G'$에서 첫 번째 전파 단계가 수행되어 조립된(coarse-grained) 예측을 생성합니다. 프레임워크는 이 단계에서 두 가지 알고리즘을 지원합니다:

• 레이블 전파 알고리즘 (LPA): 이웃의 지배력(dominance)을 기반으로 슈퍼 노드의 레이블을 반복적으로 업데이트합니다.
• 그래프 신경망 (GNN): 구체적으로, "커뮤니티" 노드와 "아이템" 노드를 포함하는 이종 그래프 표현에 GraphSAGE 아키텍처를 적용합니다. 이는 커뮤니티 수준에서의 상호작용을 모델링하여 커뮤니티-아이템 엣지를 예측합니다.

3. 커뮤니티 내 전파 (Intra-Community Propagation)

미세한 개인화를 복원하기 위해, 각 원래의 사용자 수준 서브그래프 내에서 두 번째 전파 단계가 병렬로 실행됩니다.

• 각 커뮤니티를 위해 대표 노드 $r_c$가 생성되며, 여기에는 커뮤니티 간 단계에서 집계된 레이블 정보가 포함됩니다.
• 이 노드는 커뮤니티 내의 모든 개별 사용자와 연결되어 증강된 서브그래프 $G_{c, aug}$를 형성합니다.
• LPA가 각 서브그래프에 적용되어 조립된 예측을 개별 사용자 추천으로 정교화합니다.

주요 기여

본 논문은 다음의 기여를 공식화하고 검증합니다:

1. 비즈니스 주도형 코서닝: 특정 비즈니스 규칙을 활용하여 암묵적 가족 구조를 찾아내며, 그래프 크기를 70% 이상 줄이면서도 필수적인 관계를 보존하는 기술입니다.
2. 2단계 전파 체계: 확장성(이를 위한 코스 그래프 확산)과 정확성(이를 위한 미세 조정)을 결합한 효율적인 아키텍처를 통해 낮은 지연 시간과 높은 정밀도를 보장합니다.
3. 실증적 검증: 전체 그래프 LPA 및 대안적 코서닝 방법(Louvain, Unique label-based)과의 포괄적인 비교 평가를 통해 상당한 개선을 입증했습니다.

실험 결과

프레임워크는 1,300만 명 이상의 사용자와 561개의 고유 프로모션 오퍼를 포함하는 이탈리아 TIM의 실제 통신 데이터셋을 통해 평가되었습니다.

• 효과성 (RQ1):
  • 두 단계 모두에 LPA를 사용했을 때, 제안된 방법은 전체 그래프 LPA 베이스라인 대비 NDCG@5에서 24% 향상된 성능을 보였습니다.
  • 첫 번째 단계에 경량 GNN을 통합하면 LPA 전용 버전보다 NDCG@5가 50% 이상, Louvain으로 코서닝된 그래프 기반 GNN보다 35% 더 높아졌습니다.
  • 전체 그래프 GNN 베이스라인은 메모리 부족(OOM) 오류를 발생시켜, 이 규모에서 GNN을 위한 코서닝의 필요성을 입증했습니다.
• 구조적 무결성 (RQ2):
  • 비즈니스 주도형 코서닝은 "Unique" 전략(지나치게 조밀한 커뮤니티 생성)보다 위상적 특성(차수 분포, 클러스터링 계수)을 더 잘 보존했으며, 엣지 밀도와 희소성 측면에서 Louvain 방식보다 더 나은 균형을 제공했습니다.
• 효율성 및 확장성 (RQ씨):
  • 코서닝 단계는 사전 계산 가능한 휴리스틱 덕분에 단 34초밖에 걸리지 않았습니다.
  • 전체 그래프 LPA 베이스라인은 17분 이상 소요된 반면, 제안된 방법은 2단계 LPA 프로세스를 9분 만에 완료했습니다.
  • GNN 강화 방식은 전파에 약 13분이 소요되었으나 실행 가능했던 반면, 전체 그래프 GNN은 실행 불가능했습니다.
  • 두 번째(커뮤니티 내) 전파 단계는 병렬 처리가 매우 용이하며 작은 서브그래프에서 작동하므로, 개별 사용자 추천을 위한 서브 세컨드(sub-second) 추론 시간을 가능하게 합니다.
• 절제 연구 (RQ4):
  • 전파 레이어($L$)가 증가함에 따라 성능이 향상되었으며, 댐핑 계수 $\alpha=0.5$에서 $L=5$일 때 정점에 도달했습니다. 다른 방법들과 달리, 제안된 프레임워크는 이러한 하이퍼파라미터에 명확한 민감도를 보여주었으며, 이는 코서닝된 구조 내에서의 깊은 전파가 상당한 이득을 가져온다는 것을 나타냅니다.

의의 및 주장

본 논문은 그래프 코서닝이 대규모 산업용 그래프에 GNN을 적용할 때 메모리 실패를 방지하고 계산 오버헤드를 줄여주는 데 있어 필수적이라고 주장합니다. 제안된 프레임워크는 암묵적 사회 구조(예: 가족)가 포함된 추천 작업의 경우, 비즈니스 주도형 접근 방식이 일반적인 알고리즘(예: Louvain)보다 우수함을 입증합니다.

저자들은 이 접근 방식이 확장성, 지연 시간, 추천 품질 사이의 최적의 균형을 제공한다고 강조합니다. 구체적으로:

• LPA 전용 파이프라인은 저지연 운영 환경에 즉시 배포 가능합니다.
• GNN 강화 옵션은 추가적인 훈련 비용을 감수하더라도 더 높은 예측 성능이 필요한 설정에 적합합니다.
• 이 방법은 특히 가족 중심의 오퍼에 효과적입니다. 가구 구성원 모두에게 동일한 아이템을 추천하는 것은 중복인데, 코서닝 단계는 커뮤니티 수준에서 사용자 의도를 집계함으로써 이를 자연스럽게 해결합니다.

결론적으로, 본 연구는 빈번한 사용자 상호작용 변화를 관리하면서 고품질의 추천을 유지하는 것이 중요한 실제 마케팅 캠페인에 이 코서닝 기반 접근 방식이 실질적으로 적용 가능함을 보여줍니다.