[논문 리뷰] UltraGCN: Ultra Simplification of Graph Convolutional Networks for Recommendation

 

  본 논문은 2021년 CIKM 에서 발표되었으며, 기존에 제안되었던 GCN 기반의 추천 알고리즘인 LightGCN을 수식적으로 더 간소화하여 많은 유저 수와 아이템 수를 가진 현업에서도 적용이 가능하도록 제안된 논문입니다. 해당 논문을 더욱 쉽게 이해하기 위해 이전에 연구되었던 NGCF(이전 정리), LightGCN(이전 정리)의 정리된 내용을 먼저 보시길 추천해 드립니다. 

 

논문의 리뷰는 저의 주관적인 해석과 오역이 있을 수 있습니다. 잘못된 부분이 있다면 댓글을 통해 피드백 남겨주시면 감사하겠습니다. :)

---

1. Introduction

  이전 연구를 통해 GCN(Graph Convolutional Network) 기반의 추천 모델은 전통적으로 사용되었던 CF(Collaborative Filtering) 기반의 모델보다 좋은 성능을 입증하였습니다. 하지만, 그래프의 크기가 커질수록 GCN 기반의 모델을 학습하는 데 오랜 시간이 소요되고, 메모리 이슈가 존재합니다. 이에 따라 유저와 아이템 수가 무수히 증가하는 현업에서는 GCN 기반의 모델을 적용하는 데 어려움이 있습니다. 이러한 한계를 극복하고자 경험적인 연구를 통해 feature transformations($W$)와 nonlinear activation($\sigma$) 을 제거한 LightGCN 모델이 등장하여 좋은 추천 성능과 학습 효율을 보였습니다. 하지만 본 논문의 저자들은 LightGCN의 이웃 노드들을 연결하는 message passing은 그래프 규모가 커질수록 여전히 시간이 오래 걸림을 지적하며, LightGCN에서 제안된 message passing의 한계에 대해 다음과 같이 3가지를 말합니다. 

 

(1) message passing에 존재하는 가중치 $\frac{1}{\sqrt{|N_u||N_i}}$ 는 직관적이지 않다.

(2) 모델 학습 시 발생하는 propagtaion 연산 과정에서 User-Item, Item-Item, User-User의 관계를 모델에 재귀적으로 반영시키지만, 이 다양한 관계들의 변화되는 중요성은 놓치고 있다.

(3) message passing을 전달하는 Layer가 깊어질수록 모든 노드의 정보가 비슷해지는 over-smoothing이 발생할 수 있다. 

 

  저자들은 이러한 한계점을 극복하기 위해 Ultra-Simplified form of GCNs (dubbed UltraGCN) 제안하였습니다. UltraGCN은 message passing 대신 Layer의 깊이가 무한대로 근사함을 가정한 Constraint Loss($L_c$, $L_i$)를 제안하였으며, 실험에 사용한 Amazon-Books 데이터에 대해 LightGCN 모델보다 NDCG@20에서 76.6%의 성능 항상과, 10배가 빠른 학습 속도를 보였습니다. 

2. Motivation

  LightGCN은 Layer의 깊이만큼 message passing을 통해 최종 유저 임베딩 ($e_u$) 와 아이템 임베딩 ($e_i$) 을 업데이트하게 됩니다. 이때 자기 자신을 연결하는 self-loop connection이 주어졌을 때 message passing 수식을 나타내면 아래와 같습니다. 여기서 $d_u$, $d_v$ 는 유저 노드의 차수, $d_i$, $d_k$ 는 아이템 노드의 차수를 의미합니다. 

 

 

  유저-아이템에 대한 선호도 ($\hat{y}$) 를 얻기 위해 유저 임베딩 ($e_u^{l+1}$) 과 아이템 임베딩 ($e_i^{l+1}$) 의 dot-product를 수행하는데, 이를 수식으로 나열하면 다음과 같습니다. 수식의 $u$, $v$는 유저를 의미하고, $i$, $k$는 아이템을 의미합니다. 전통적인 CF는 $e_u$ $\cdot$ $e_i$ 를 통해 collaborative signal을 포착했다면 GCN은 $e_{i}$ $\cdot$ $e_k$, $e_u$ $\cdot$ $e_v$, $e_k$ $\cdot$ $e_v$ 을 통해 유저-유저, 아이템-아이템 등의 다양한 관계의 collaborative signal 정보를 얻을 수 있습니다. 

 

$\alpha$ 에 대한 세부 가중치를 나열하면 다음과 같습니다. 

 

 

  그러나 노드 간의 관계 앞에 붙은 엣지 가중치 $\alpha_{ik}$, $\alpha_{uv}$ 는 비대칭적인 구조로 collaborative signal을 포착하는데, 한계가 있습니다.  $\alpha_{ik}$를 보면 아이템 $k$에대해선 $\frac{1}{\sqrt{d_{k}+1}}$, 아이템 $i$에 대해선 $\frac{1}{d_{i}+1}$으로 비대칭적으로 가중치가 더해지게 됩니다. 이경우 애매모호한 관계와 noisy, uninformative 등으로 학습의 효율과 추천 성능이 떨어질 수 있습니다. 

3. UltraGCN

  이러한 message passing의 한계와 GCN 학습이 오래걸리는 비효율을 극복하기 위해 UltraGCN이 제안되었습니다. Messsage passing을 통해 User-Item, Item-Item, User-User의 정보를 학습하는 것이 아닌, User-Item 간의 constraint loss ($L_C$)와 Item-Item 간의 constaint loss($L_I$)를 통해 다양한 관계를 학습합니다. 

Learning on User-Item Graph

  먼저 User-Item 간의 관계를 학습하기 위해 message passing을 전달하는 레이어($L$)의 깊이가 무한대로 보내 수렴한다고 가정하면 아래와 같은 식으로 표현될 수 있습니다. 

 

 

이웃 노드들로부터 집계된 중심 노드는 일정 값에 대해 수렴하여 $e_u$ 으로 나타나는데, 이를 수식(3)에 대입하면 아래와 같이 표현 될 수 있습니다. 

이를 $e_u$에 대해 정리하면 이웃 노드들을 집계하는 임베딩 벡터 $e_i$ 와 상호작용 가중치 $\beta_{ui}$로 표현될 수 있습니다. $\beta_{ui}$ 수식을 통해서 만약 유저 노드에 연결된 아이템 노드들이 많다면 노드 간의 상호작용이 낮은 가중치 값을 갖는 것을 알 수 있습니다. 

목적함수를 계산하기 위해 $e_u$와 $e_i$의 내적 값이 최대가 되도록 학습합니다. 내적을 최대화 한다는 것은 코사인 유사도를 최대화 한다는 것을 의미하고, 결국 중심 노드와 이웃된 노드들끼리의 벡터값이 유사해 지도록 학습이 진행됩니다. 

 

학습 과정에서 손쉬운 최적화를 위해 sigmoid ($\sigma$)와 negative log likelihood($-log$)를 첨가하여 constraint loss($L_c$)를 도출해 냈습니다. 여기서 $\beta_{u,i}$는 constraint coefficient로 사용됩니다. 

 

하지만 레이어의 깊이가 극한으로 수렴함을 가정한 UltraGCN 같은 경우 $\beta_{u,i}$가 모든 유저 - 아이템 쌍을 연결하여 노드 간의 정보가 동일해지는 over-smoothing 문제가 야기될 수 있습니다. 이에 따라 LightGCN은 message passing layers를 2~4로 제한하였지만, message passing layers를 극한으로 가정한 UltraGCN 에서는 negative sampling을 통해 위 문제를 해결하였습니다. 아래 수식에서 summation $U$는 간결한 표현을 위해 생략하였습니다.

User-Item의 관계를 학습하는 손실함수 $L_C$와 전형적으로 CF 학습에 사용되는 BCE-Loss를 메인 Optimization($L_O$)으로 채택하여 $UltraGCN_{base}$에 사용되는 손실함수를 제안하였습니다. 여기서 $\lambda$는 두 Loss term을 조절하는 하이퍼 파라미터 importance weight입니다. 

Learning on Item-Item Graph

  UltraGCN은 message passing을 직접적으로 사용하지 않아 위 Motivation에서 한계로 언급된 Item-Item, User-User 간의 비대칭적인 연산으로부터 벗어나 유연하게 학습을 할 수 있습니다. Item-Item에 대한 가중치를 계산하기 위해 유저-아이템의 관계가 포함된 인접행렬($A$)을 전치시켜 Item-Item co-occurrence graph를 만들었으며, 수식(9)에 따라 아이템 노드의 차수를 통해 Item-Item의 가중치를 조정하는 $\omega_{i,j}$를 제안하였습니다. 

 

 

Item-Item 관계는 User-Item 관계에 비해 훨씬 밀도가 높아 신뢰할 수 없거나, 노이즈로 인해 학습을 어렵게 만들 수 있습니다. 이에 따라 모든 이웃된 아이템 노드를 계산하는 것이 아닌 가중치  $\omega_{i,j}$에 따라 상위 K개의 유사한 아이템 $S(i)$를 선택하여 학습을 진행합니다. 이때 목적함수 $L_I$ 는 $UltraGCN_{Base}$의 Loss function과 동일하게 적용하여 multi-task learning을 수월하게 합니다. 앞선 $L_O$, $L_C$의 Negative sampling을 통해 over-smooting 문제를 해결할 수 있었기 때문에 $L_I$에선 이를 생략하였습니다. 

 

 

최종적으로 constraint loss를 통해 User-Item, Item-Item 관계의 중요도가 반영된 UltraGCN의 수식은 아래와 같으며, $\lambda$와 $\gamma$는 이들의 중요도를 조정하는 하이퍼파라미터입니다. 

 

 

모델 학습이 끝나고 최종 추천은 기존의 CF 방식과 마찬가지로 $e_u$와 $e_i$의 dot-product를 통해 상위 스코어 $K$개를 추천하게 됩니다. GCN 학습 과정에서 User-User의 관계를 고려하여 실험을 진행해 보았지만, 폭 넓은 User-User의 관계로 성능이 좋지 않아 제외하였다고 합니다. 

 

저자가 말하는 UltraGCN의 장점 및 특징은 다음과 같습니다. 먼저 User-Item, Item-Item 들의 다양한 노드 간의 연결성을 constraint loss에 사용되는 $\beta$, $\omega$ 가중치를 통해 보다 합리적이고 해석이 가능하게 전달됩니다. 또한 각각의 constraint loss에 $\lambda$와 $\gamma$라는 하이퍼 파라미터를 통해 다양한 관계의 중요도를 유연하게 학습할 수 있습니다. 마지막으로 제안된 목적함수는 multi-task learning을 수행하지만, 실제로는 binary cross entropy 손실함수로 통합되어 있어 학습에 용이 및 빠른 수렴이 가능합니다. 

4. Experiments

저자들은 기존 GCN 기반의 추천 연구에 사용된 4가지 데이터 셋을 통해 실험을 진행하였습니다. 

Performance Comparison

다른 추천시스템 모델들과 성능을 비교한 결과 UltraGCN의 성능이 더 우월한것을 알 수 있습니다.

Efficiency Comparison

아래의 Table 3. 을 보면 MF-BPR과 UltraGCN의 Time/Epochs 이 유사한 것을 알 수 있습니다. 이는 본 글에선 생략하였지만, 논문의 3.3.3 절에 언급된 UltraGCN의 훈련 과정의 시간 복잡도가 MF의 시간 복잡도가 동일한 수준임을 증명합니다. #Epoch 같은 경우에도 기존의 GCN기반의 모델들 보다 훨씬 적은 Epoch으로 학습이 완료되어 UltraGCN의 효율성을 입증합니다. 

 

마찬가지로 Table 4.를 통해 전체 모델을 75 epoch으로 고정 놓고 다른 모든 비교 모델 성능 측정 결과 UltraGCN의 성능이 압도적인 것을 알 수 있습니다. 이는 UltraGCN이 더 짧은 시간 동안 훨씬 더 좋은 성능을 달성할 수 있다는 것을 의미합니다. 

5. Conclusion

본 논문은 기존 GCN 기반의 추천에서 message passing은 대규모 데이터 셋에서 학습이 오래 걸릴 뿐만 아니라 다양한 User-Uesr, Item-Item의 관계를 학습하는데 합리적이지 않음을 지적합니다. 이에 따라 message passing이 무한으로 수렴했다고 가정하고 User-Item, Item-Item의 관계를 학습할 수 있는 constraint loss를 제안하여 SOTA의 성능 뿐만 아니라 LightGCN 보다 10배의 빠른 속도를 보였습니다. 개인적으로 현업에선 그래프 기반의 추천시스템을 적용하기 위해 그래프 규모, 학습 속도 등의 이슈로 적용이 어려운데, 이를 해결할 수 있는 좋은 논문이었습니다.