CS224W - (13) GNNs for Recommender System

추천 시스템: 태스크와 평가

인터넷이 널리 보급되고 나서 수많은 정보가 폭발적으로 증가하였습니다. 넷플릭스에는 1만 개가 넘는 작품이 있고, 아마존에는 1,200만 개에 이르는 상품이 있고, 스포티파이는 7천만 개 이상의 수록곡을 보유하고 있습니다. 유튜브는 100억 개가 넘는 영상을, 핀터레스트는 2,000억 개가 넘는 이미지를 제공하고 있죠. 이렇게 많은 정보를 제공받을 수록 개인화된 추천의 중요성이 각광을 받습니다. 여기서 개인화된 추천은 수많은 아이템 중 일부 아이템만을 사용자에게 제공하는 것을 말합니다.

Recommender system can be naturally modeled as a bipartite graph.

추천 시스템은 기본적으로 이분 그래프(bipartite graph) 형태로 나타낼 수 있습니다. 이 그래프에는 사용자, 아이템의 두 가지 노드 타입이 있습니다. 이 두 노드를 연결하는 엣지는 사용자-아이템 상호작용을 의미합니다. 예를 들자면 클릭, 구매, 리뷰 등이 있겠죠. 이 엣지는 종종 상호작용이 나타난 시간하고도 관련이 있습니다. 보통 추천 태스크라고 하면 과거의 사용자-아이템 상호작용을 이용해서 앞으로 각 사용자가 소비할 아이템을 예측하게 됩니다. 이런 스키마는 링크 예측 태스크로도 나타낼 수도 있습니다. 따라서 노드 $u \in U$, 노드 $v \in V$에 대해서 다음 스코어 $f(u, v)$를 계산하는 것과 같습니다.

2-stage process for modern recommender system

하지면 현대의 추천 시스템은 모든 사용자-아이템 쌍에 대한 스코어를 계산할 수 없습니다. 너무 많은 사용자와 아이템이 있기 때문이죠. 그래서 최근엔 두 단계의 추천 시스템을 많이 사용합니다. 우선 추천 후보군을 빠르게 생성하고 그 후보군에 대한 순위를 학습/추론하는 단계를 거칩니다. 가장 많이 사용하는 추천 방식은 Top-K 추천입니다. 각 사용자에게 $K$ 개의 아이템을 추천하는 방식입니다. 이때 추천의 효과를 높이기 위해서 $K$는 상대적으로 작은 값으로 사용합니다. 보통 10에서 100 정도의 값을 사용합니다. Top-K 추천의 목표는 $K$ 개의 아이템에 사용자가 미래에 소비할 아이템을 최대한 많이 포함시키는 것입니다. 이를 위한 평가 메트릭으로 Recall@K를 사용합니다.

사용자 $u$에 대해서 $P_u$를 사용자가 미래에 상호작용할 아이템의 집합, $R_u$를 모델이 사용자에게 제공한 추천 아이템 집합이라고 두겠습니다. 당연히 $|R_u| = K$가 되고 이때 사용자가 이미 상호작용한 아이템은 $R_u$에서 제외합니다. Recall@K 는 다음과 같이 정의합니다.

\[\text{Recall}@K = \frac{|P_u \cap R_u|}{|P_u|}\]

이 값은 높을 수록 좋으며 모든 사용자에 대해서 Recall@K의 평균을 최종 메트릭으로 사용합니다.

추천 시스템: 임베딩 기반 모델

사용자의 집합을 $U$, 아이템의 집합을 $V$, 이미 가지고 있는 사용자-아이템 상호작용을 $E$라고 두고 다음과 같이 정의합니다.

\[E = \{ (u, v) \mid u \in U, v \in V, u \text{ interacted with } v \}\]

Top-K 아이템을 얻기 위해서 사용자-아이템 상호작용에 대한 스코어링 함수가 필요합니다. 위에서 다루었듯이 이 스코어링 함수는 두 노드 $u$, $v$간의 스코어이며, 이 스코어가 높고 사용자와 상호작용하지 않은 $K$ 개의 아이템을 사용자에게 추천합니다. 위 그림에서는 $K=2$에 대해 스코어가 가장 높은 $v_1$과 $v_3$이 추천됩니다.

우리는 이때 사용자-아이템 상호작용에 스코어를 매기기 위해 임베딩 기반 모델을 고려할 수 있습니다. 사용자 $u \in U$에 대해 $D$ 차원 임베딩 $\mathbf{u} \in \mathbb{R}^D$, 아이템 $v \in V$에 대해 $D$ 차원 임베딩 $\mathbf{v} \in \mathbb{R}^D$으로 둘 수 있습니다. 이때 파라미터화한 함수 $f_\theta(\cdot, \cdot) : \mathbb{R}^D \times \mathbb{R}^D \mathbb{R}$가 있고, 이 함수가 바로 스코어링 함수가 됩니다.

\[\text{score}(u, v) \equiv f_\theta(\mathbf{u}, \mathbf{v})\]

이렇게 임베딩 기반 모델은 사용자 임베딩, 아이템 임베딩, 스코어링 함수의 총 세 가지 종류의 파라미터가 있습니다. 우리는 학습 데이터 내의 사용자-아이템 상호작용을 많이 맞추는, 즉 높은 Recall@K를 달성하는 모델 파라미터를 최적화하면 됩니다. 그리고 테스트 데이터에 대해서도 높은 Recall@K 를 보이면 더 좋겠죠.

하지만 Recall@K 는 미분 불가능합니다. 따라서 기울기 강하법과 같은 기울기 기반의 최적화 방법을 사용할 수 없습니다. 이로 따라 Recall@K를 대체할 수 있는 효율적인 두 가지 기울기 기반 최적화 손실 함수를 사용합니다.

• Binary loss
• Bayesian Personalized Ranking (BPR)

이 함수들은 모두 미분 가능하며 기존 학습 목적에도 잘 부합합니다.

Binary Loss

학습 데이터에 있는 엣지 집합 $E$와 사용자와 아이템간 상호작용이 없는 노드쌍 집합 $E_\text{neg}$가 있을 때 binary loss는 다음과 같습니다.

\[- \frac{1}{|E|} \sum_{(u, v) \in E} \log(\sigma(f_\theta(\mathbf{u}, \mathbf{v}))) - \frac{1}{E_\text{neg}} \sum_{(u, v) \in E_\text{neg}} \log (1 - \sigma(f_\theta(\mathbf{u}, \mathbf{v})))\]

Binary loss는 $E$에 속한 엣지의 스코어를 $E_\text{neg}$에 속한 엣지보다 높게 만듭니다. 그런데 위 그림처럼 엣지 $(u_0, v_0)$는 $E$에 속하는 positive edge지만 negative edge인 $(u_1, v_0)$보다 스코어가 낮은 경우에 모델은 negative edge가 positive edge보다 스코어가 높기 때문에 계속해서 페널티를 주게 됩니다. 결국 $E$에 속한 모든 엣지를 $E_\text{neg}$에 속한 모든 엣지보다 높게 만들어서 사용자마다 개인화된 추천이 이루어지지 않게 됩니다. 하지만 Recall@K는 개인화된 메트릭이기에 binary loss는 적절하지 않습니다. 결국 Recall@K를 대체하는 손실 함수는 개인화된 방법으로 작동해야 하는데 BPR이 바로 이 문제를 해결해줍니다.

Bayesian Personalized Ranking (BPR)

BPR은 개인화된 대체 손실 함수입니다. BPR은 사용자별로 positive edge와 negative edge를 구분하여 손실 함수를 계산합니다. 사용자별 Positive edge와 negative edge는 다음과 같습니다.

\[E(u^\ast) \equiv \{ (u^\ast, v) \mid (u^\ast, v) \in E \}\] \[E_\text{neg}(u^\ast) \equiv \{ (u^\ast, v) \mid (u^\ast, v) \in E_\text{neg} \}\]

이제 사용자마다 positive edge의 스코어를 negative edge의 스코어보다 높여주도록 계산하면 됩니다. 사용자 $u^\ast$에 대한 BPR loss는 다음과 같습니다.

\[\text{Loss}(u^\ast) = \frac{1}{|E(u^\ast)| \cdot |E_\text{neg}(u^\ast)|} \sum_{(u^\ast, v_\text{pos} ) \in E(u^\ast)} \sum_{(u^\ast, v_\text{neg}) \in E_\text{neg}(u^\ast)} - \log \left(\sigma(f_\theta(\mathbf{u}^\ast, \mathbf{v}_\text{pos}) - f_\theta(\mathbf{u}^\ast, \mathbf{v}_\text{neg})) \right)\]

그리고 위 식을 이용해 모든 사용자에 대해서 다음과 같이 계산합니다.

\[\frac{1}{|U|} \sum_{u^\ast \in U} \text{Loss}(u^\ast)\]

위 BPR 식은 미니배치를 이용하여 근사시킬 수 있는데요. 각 미니배치마다 사용자를 샘플링합니다. 그리고 각 사용자 $u^\ast \in U_\text{mini} \subseteq U$에 대해서 하나의 포지티브 아이템 $v_\text{pos}$와 샘플링한 네거티브 아이템 $V_\text{neg} = \{v_\text{neg}\}$를 샘플링합니다. 미니배치 손실 함수는 다음과 같이 계산합니다.

\[\frac{1}{|U_\text{mini}|} \sum_{u^\ast \in U_\text{mini}} \frac{1}{|V_\text{neg}|} \sum_{v_\text{neg} \in V_\text{neg}} - \log(\sigma (f_\theta(u^\ast, v_\text{post}) - f_\theta(u^\ast, v_\text{neg})))\]

임베딩 기반 모델이 잘 작동하는 이유는 협업 필터링에서 찾을 수 있습니다. 협업 필터링은 자신과 유사한 사용자의 선호도를 모아서 사용자에게 추천을 해줍니다. 자신과 비슷한 사용자들은 비슷한 아이템을 선호한다는 가정이 기저에 깔려있습니다. 이때 가장 중요한 요소는 사용자 간 유사도를 계산하는 것인데 임베딩은 강제로 사용자나 아이템 간 유사도를 잡아낼 수 있습니다. 이를 통해 모델은 아직 알지 못하는 사용자-아이템 상호작용을 효과적으로 예측할 수 있습니다.

Neural Graph Collaborative Filtering (NGCF)

전통적인 협업 필터링(collaborative filtering)은 얕은 인코더(shallow encoder)에 기반을 두고 있습니다. 그렇기 때문에 사용자 피처나 아이템 피처는 사용하지 않습니다. 각 사용자 $u \in U$와 아이템 $v \in V$에 대해 학습 가능한 얕은 임베딩(shallow embedding) $\mathbf{u}, \mathbf{v} \in \mathbb{R}^D$를 생성합니다. 스코어링 함수로는 단순 내적을 사용합니다.

\[f_\theta(\mathbf{u}, \mathbf{v}) \equiv \mathbf{z}_u^T \mathbf{z}_v\]

하지만 얕은 인코더는 모델 그 자체만으로 그래프의 구조를 잡아내기 힘들고 학습 목적 함수로 일차원적인 구조만을 잡아낼 수 있습니다. 다시 말해서 멀티홉 관계는 전혀 잡아내지 못합니다. 이런 문제를 해결하기 위해서 나온 알고리즘이 Neural Graph Convolution Filtering입니다.

Overview of Neural Graph Collaborative Filtering

NGCF는 사용자/아이템 임베딩을 생성할 때 고차원적인 그래프 구조를 명시적으로 통합합니다. 다시 말해서 멀티홉 관계를 잡아낼 수 있게 됩니다. 사용자-아이템에 대한 이분 그래프가 주어졌을 때 우선 각 노드에 대해 학습 가능한 얕은 임베딩을 생성합니다. 그리고 다중 레이어 GNN을 사용하여 이분 그래프에 임베딩을 전파시킵니다. 이를 통해서 고차원 그래프 구조를 잡아냅니다. 이때 두 종류의 파라미터가 같이 학습되는데 하나는 사용자/아이템 임베딩이고 다른 하나는 GNN의 파라미터입니다.

좀 더 자세히 살펴보자면 노드 임베딩을 초기화할 때 노드 피처로 초기화를 합니다. 각 사용자 $u \in U$에 대해서 $h_u^{(0)}$을 사용자의 얕은 임베딩으로, 각 아이템 $v \in V$에 대해서 $h_u^{(0)}$을 아이템의 얕은 임베딩으로 초기화합니다.

그리고 사용자 임베딩은 연결되어 있는 아이템 노드의 임베딩을 집계하여 업데이트하고 아이템 임베딩은 연결되어 있는 사용자 노드의 임베딩을 집계하여 업데이트를 반복적으로 진행합니다.

\[h_v^{(k+1)} = \text{COMBINE}\left( h_v^{(k)}, \text{AGGR} \left( \{ h_u^{(k)} \}_{u \in N(v)} \right) \right)\] \[h_u^{(k+1)} = \text{COMBINE}\left( h_u^{(k)}, \text{AGGR} \left( \{ h_v^{(k)} \}_{u \in N(u)} \right) \right)\]

이런 반복을 통해 멀티홉 관계를 잡아내게 됩니다. $\text{AGGR}$과 $\text{COMBINE}$을 어떻게 설정하느냐에 따라 다른 아키텍쳐를 만들 수 있습니다. $\text{AGGR}(\cdot)$은 평균으로, $\text{COMBINE}(\mathbf{x}, \mathbf{y})$는 $\text{ReLU(Linear(Concat(}\mathbf{x}, \mathbf{y} \text{)))}$로 보통 사용합니다.

이웃 집계를 $K$ 번 반복하고 나면 최종 사용자/아이템 임베딩인 $\mathbf{h}_u^{(K)}$, $\mathbf{h}_v^{(K)}$ 를 얻게 됩니다. 마지막으로 다음과 같이 설정하면 됩니다.

\[\mathbf{u} \leftarrow \mathbf{h}_u^{(K)}, \qquad \mathbf{v} \leftarrow \mathbf{h}_v^{(K)}\]

스코어링 함수는 내적을 사용합니다.

\[\text{score}(\mathbf{u}, \mathbf{v}) = \mathbf{u}^T \mathbf{v}\]

LightGCN

NGCF에선 얕은 임베딩을 사용하였는데 사실 얕은 임베딩만으로도 충분한 표현력을 가질 수 있습니다. 모든 사용자/아이템 노드에 대해서 임베딩을 학습하는데 노드의 수가 충분히 많기 때문이죠. 임베딩 차원의 크기 $D$보다 일반적으로 노드의 수 $N$이 더 큰데 얕은 임베딩은 $O(ND)$, GNN 은 $O(D^2)$ 이기 때문입니다. 그래서 GNN의 파라미터는 성능에 크게 영향을 주지 않을 수도 있습니다.

LightGCN은 이런 관찰을 통해 NGCF를 다음 방법으로 단순화하여 성능을 높였습니다.

• 이분 그래프를 위한 인접 행렬 생성
• GCN의 행렬화
• 비선형성을 제거하여 GCN을 단순화

Shallow embedding matrix

이분 그래프를 인접 행렬로 나타내면 위 그림과 같습니다. 인접 행렬 $A$의 차원은 사용자의 수와 아이템의 수를 합친 것과 같습니다.

이번엔 GCN을 행렬식으로 바꿔보겠습니다. $A$의 degree matrix를 $D$라고 두었을 때 정규화한 인접 행렬 $\tilde{A}$ 를 다음과 같이 정의할 수 있습니다.

\[\tilde{A} \equiv D^{-1/2} A D^{ -1/2}\]

$k$ 번째 레이어의 임베딩 행렬을 $E^{(k)}$라고 했을 때 GCN의 집계 레이어를 다음 행렬 형태로 쓸 수 있습니다.

\[E^{(k+1)} = \text{ReLU} (\tilde{A}E^{(k)}W^{(k)})\]

여기서 $\tilde{A}E^{(k)}$는 이웃 집계, $W^{(k)}$는 학습 가능한 선형 변환입니다. 이제 여기에서 ReLU를 제거하여 선형성을 빼서 GCN을 단순화합니다.

\[E^{(k+1)} = \tilde{A}E^{(k)}W^{(k)}\]

마지막 노드 임베딩 행렬은 다음과 같이 다시 쓸 수 있습니다.

\[\begin{aligned} E^{(K)} &= \tilde{A} E^{(K-1)} W^{(K-1)} \\ &= \tilde{A}\left(\tilde{A} E^{(K-2)} W^{(K-2)}\right)W^{(K-1)} \\ &= \tilde{A} \left( \tilde{A} \left( \cdots \left( \tilde{A}E^{(0)}W^{(0)}\right) \cdots \right) W^{(K-2)} \right) W^{(K-1)} \\ &= \tilde{A}^K E \left( W^{(0)} \cdots W^{(K-1)} \right) = \tilde{A}^K E W \end{aligned}\]

ReLU를 제거하면 이처럼 GCN을 단순하게 만들 수 있습니다. 식만 살펴보면 Correct&Smooth처럼 노드 임베딩이 그래프 전체로 확산되는 형태입니다. 간단하게는 $E \leftarrow \tilde{A}E$를 $K$ 번 하는건데 각 행렬 곱이 현재 임베딩을 노드의 이웃으로 확산되는 알고리즘입니다.

그리고 과한 smoothing을 방지하기 위해서 다음의 multi-scale diffusion을 고려할 수 있습니다.

\[\alpha_0 E^{(0)} + \alpha_1 E^{(1)} + \cdots + \alpha_K E^{(K)}\]

위 식대로라면 임베딩을 멀티홉 규모로 확산할 수 있습니다. $\alpha_0 E^{(0)} = \alpha_0 \tilde{A}^0 E^{(0)}$ 은 일종의 self-connection이고, $\alpha_0, \cdots, \alpha_K$는 하이퍼파라미터입니다. LightGCN에서는 간단하게 $\alpha_K = \frac{1}{K+1}$ 로 사용합니다.

이런 간단한 확산 전파(diffusion propagation)이 잘 작동하는 이유는 확산 그 자체로 유사한 사용자/아이템 임베딩이 실제 비슷한 위치에 있도록 만들기 때문입니다. 유사한 사용자나 아이템은 공통의 이웃을 가지고 있고 미래에도 비슷한 선호도를 보일 것으로 예상하기 때문이죠.

GCN/C&S 와의 연관성

LightGCM의 임베딩 전파는 GCN/C&S와 밀접한 연관이 있습니다. GCN/C&S의 이웃 집계 부분은 다음과 같습니다.

\[\mathbf{h}_v^{(k+1)} = \sum_{u \in N(v)} \frac{1}{\sqrt{d_u} \sqrt{d_v}} \cdot \mathbf{h}_u^{(k)}\]

여기에는 자기 자신에 대한 루프도 포함되어 있습니다. LightGCN은 비슷한 식을 사용하지만 자기 자신에 대한 루프는 포함되어 있지 않고 마지막 임베딩에서 모든 레이어의 임베딩의 평균을 사용합니다.

\[\mathbf{h}_v = \frac{1}{K+1} \sum^K_{k=0} \mathbf{h}_v^{(k)}\]

행렬 분해(Matrix Factorization)과의 비교

LightGCN과 얕은 인코더 모두 사용자와 아이템에 대한 고유 임베딩을 학습한다는 공통점이 있습니다. LightGCN의 차이점이라면 스코어링 시 확산된 사용자/아이템 임베딩을 사용한다는 점입니다. 행렬 분해는 사용자/아이템 임베딩에 직접 스코어링을 합니다. 이로 인해 LightGCN의 성능이 얕은 인코더보다 낫지만 추가적인 확산 계산으로 인해 계산적 비용은 더 높습니다.

PinSAGE

PinSAGE는 Pinterest에서 개발한 추천 알고리즘으로 이미지, 텍스트, 그래프 정보를 모두 통합한 모델입니다. GCN을 이용하여 배포된 서비스 중에 업계에서 가장 큰 서비스로 새로운 콘텐츠에 대해서도 잘 작동하고 핀을 생성하고 몇 초 안에 바로 사용할 수 있습니다.

PinSAGE의 목표는 수십억 개의 오브젝트가 포함된 대규모의 Pinterest 그래프에서 노드에 대한 임베딩을 생성하는 것입니다. 이에 대한 핵심 아이디어는 근처에 있는 노드로부터 정보를 빌려오는 것입니다.

실제 정원의 울타리와 침대의 레일은 비슷하게 생겼지만 문과 침대는 그래프에서 인접할 확률이 매우 적다는 점을 활용하는 것이죠. 핀 임베딩은 추천, 분류, 랭킹 등 다양한 태스크에서 매우 중요하게 사용됩니다.

PinSAGE 논문에서는 수십억 개에 달하는 노드나 엣지를 사용하는 추천 시스템을 위한 여러 가지 기법들을 소개하였습니다.

• 미니 배치 내 사용자간 공유되는 네거티브 샘플
• 하드 네거티브 샘플
• 커리큘럼 학습
• 큰 그래프에 대한 미니 배치 GNN 학습

PinSAGE 모델에서 수행하는 태스크를 요약해보자면 사용자에게 관련된 핀을 추천해주는데 다음과 같은 방식으로 임베딩을 학습하는 것입니다.

\[d(z_\text{cake1}, z_\text{cake2}) < d(z_\text{cake1}, z_\text{sweater})\]

네거티브 샘플 공유

위에서 BPR loss에 대해서 다룰 때 BPR loss는 미니 배치 내 사용자에 대해서 하나의 포지티브 아이템과 샘플링한 네거티브 아이템 집합을 학습에 사용하였습니다. 여기서 사용자마다 네거티브 샘플을 더 추가하면 성능 향상을 할 수 있지만 계산 비용이 높아집니다. 그래서 네거티브 샘플을 미니 배치 내 사용자끼리 공유하는 방식으로 이 문제를 해결했습니다. 기존의 방식대로라면 $|U_\text{mini}| \cdot | V_\text{neg} |$ 만큼의 임베딩을 생성해야 하지만 미니 배치 내 사용자가 네거티브 샘플을 공유하면 생성해야 할 임베딩은 $|V_\text{neg}|$로 줄어들게 됩니다. 이런 방법을 사용하더라도 눈에 띌 만한 성능의 저하는 없었다고 합니다.

하드 네거티브와 커리큘럼 학습

실제 서비스에서 사용해야 하는 추천 시스템은 매우 세분화된 예측을 해야 합니다. 실제 아이템 수는 수십억 개에 달하지만 사용자에게 추천하는 아이템은 고작 10~100개니까요. 이로 인해 발생할 수 있는 문제는 네거티브 샘플 공유에서 샘플링할 때 임의로 샘플링을 진행한다는 것입니다. 이 샘플 중 대부분은 포지티브 아이템과 크게 구분할 필요 없는 소위 말하는 이지 네거티브(easy negative) 입니다. 그래서 모델의 결과를 더 높여줄만한 하드 네거티브(hard negative) 를 샘플링 해야합니다. 위 그림에서 볼 수 있듯이 아예 관련 없는 핀을 하드 네거티브 아이템으로 정의합니다.

이때 커리큘럼 학습(curriculum learning) 을 수행하는데 학습이 진행될 수록 더 하드한 샘플을 사용하는 것입니다. $n$ 번째 epoch에선 $n-1$ 개의 하드 네거티브 아이템을 추가하는 형식입니다. 그러면 모델은 점차 세분화된 예측을 하는 방법을 학습합니다.

각 사용자 노드에 대해 하드 네거티브 아이템은 그래프에서 사용자 노드에 가깝지만 연결되어 있지 않은 노드입니다. 사용자 $u \in U$에 대해 하드 네거티브 아이템은 다음과 같이 얻어집니다.

• 사용자 $u$에 대해서 개인화된 페이지 랭크(personalized page rank, PPR)를 계산
• 아이템을 PPR 내림차순으로 정렬
• PPR 점수가 적당히 높은 아이템(2000~5000위)을 랜덤 샘플링

이런 하드 네거티브 아이템은 공유 네거티브 샘플에도 사용됩니다.

Fine-grained object similarity