1. Background
기존의 CF( Collaborative Filtering )에는 다음과 같은 가정이 존재한다.
비슷한 행동을 하는 유저들이 비슷한 아이템을 선호할 것이다.
이러한 가정에서 유저들이 갖는 성향을 잠재요인( Latent Factor )이라고 하며, 직접적으로 관찰되거나 측정되지 않는 요인을 말한다. CF는 유저와 아이템 각각의 임베딩 벡터를 생성하고, 내적을 통해 유저가 선호할만한 아이템의 스코어를 계산한다. 이에 더해 그래프에 기반한 추천모델인 NGCF( Neural Graph Collaborative Filtering )는 유저와 아이템 임베딩 벡터를 Embedding Propagation Layer를 통과시켜 업데이트함으로써 유저가 선호할만한 아이템의 스코어를 계산하여 추천한다. 여기서 문제는 NGCF가 GCN 구조를 차용하여 Embedding Propagation을 사용했다는 점이다. GCN의 본래 목적은 node들에 포함된 정보들을 convolution하여 classification 문제를 해결하는 것이므로, 유저와 아이템 간의 연결성을 표현한 CF 구조에서는 적절하지 않는다는 것이었다.
LightGCN은 GCN의 구조에서 Ablation Study를 통해 본래 목적과 연관이 없는(적은) 모듈을 제외하고, 간소화된 설계를 통해 추천시스템에 적합하게 만든 모델이다.
2. Preliminaries
2-1. NGCF Brief
우선, NGCF 모델의 Embedding Propagation Rule을 보자.
여기서, $e_{u}^{k}$와 $e_{i}^{k}$는 각각 유저 u와 아이템 i의 k번째 레이어 후의 정제된 임베딩을 나타낸다. 또, $N_{u}$와 $N_{i}$는 각각 유저와 아이템 노드에 연결된 첫번째 hop의 차수를 의미하며, $W_{1}$과 $W_{2}$는 trainable weights이다.
위의 수식을 해석하면, k+1번째 유저와 아이템 각각의 임베딩은 k번째의 유저와 아이템의 임베딩으로 표현된다.
대표로 $e_{u}^{k+1}$을 보자.
$e_{u}^{k+1}$은 $e_{u}^{k}$와 k번째 레이어까지 상호작용한 모든 레이어의 임베딩이 propagation된 값을 더한다. propagation은 element-wise product을 통해 계산된다. $ \frac{1}{\sqrt{\left| N_{u} \right|\left|N_{i} \right|}}$는 GCN의 $p_{ui}$로, 정규화된 라플라시안 매트릭스의 값이다. (다른 표현으로 Graph Laplacian Norm이라고도 하며, NGCF 논문에서는 discount factor로 표현하기도 한다. 본 논문에서는 Symmetric Normalization Term) 이는 u-i 엣지에서 얼만큼 주변 node의 정보를 반영할지의 정도를 말한다.
Graph Laplacian Matrix는 다음과 같은 과정을 통해 연산된다.
여기서 중요한 점은,
$W_{1}e_{u}^{k}$와 $W_{1}e_{i}^{k}$를 통한 self-connection으로 이전 레이어의 임베딩 정보를 유지하고, $W_{1}$와 $W_{2}$를 통한 feature transformation과 $\sigma $ ( nonlinear activation )을 사용해 임베딩 값을 업데이트한다는 것이다.
2-2. Empirical Explorations on NGCF
논문에서는 NGCF를 실험한 조건과 같은 환경에서 데이터셋에 대해 3가지 측면의 ablation study를 진행하였다.
- NGCF-f : feature transformation 제거
- NGCF-n : non-linear activation 제거
- NGCF-fn : feature transformation과 non-linear activation 제거
위의 그림을 보면, 기존의 NGCF보다 non-linear activation만 제거했을때 성능이 저하되었지만, feature transformation만 제거하거나 둘 다 제거했을때의 성능이 월등히 향상된 것을 볼 수 있다. 이에 근거하여 논문에서는 추천시스템을 구성할 때, 구조의 각 요소가 어떤한 영향력을 갖는지 ablation study를 하는 것이 중요하다고 강조하며, CF에 적용하기 위한 GCN의 필수요소( neighborhood aggregation )만을 포함한 LIghtGCN 모델을 제안했다.
3. Method
두 모델의 구조를 보면 공통적으로 임베딩 벡터를 입력으로 한다. NGCF는 feature transformation을 포함한 Embedding Propagation Layer를 통과하고, LightGCN은 각각의 임베딩 벡터를 Normalized Sum을 통해 Propagation을 진행한다. 이후, NGCF는 각각의 레이어에서 산출된 임베딩 벡터들을 concat하여 유저와 아이템의 스코어를 계산하고, LightGCN은 Layer Combination( Weighted Sum )을 통해 스코어를 계산한다.
최종적으로 계산된 스코어를 통해 유저가 구매하지 않은 아이템 중 상위 k개의 아이템을 유저에게 추천한다.
3-1-1. LightGCN
논문에서는 Embedding Propagation Layer에서 feature transformation과 non-linear activation, self-connection을 제거하고 아래와 같은 새로운 Embedding Propagation Rule을 제안한다. 이때, symmetric normalization term( graph laplacian norm )의 $N_{u}$와 $N_{i}$는 각각 유저와 아이템 노드에 연결된 첫번째 hop의 차수를 의미하고, convolution 연산을 수행하며 임베딩 값이 커지지 않도록 정규화하는 역할을 한다.
새롭게 정의된 Embedding Propagation Rule은 다음과 같다.
3-1-2. Layer Combination & Model Prediction
k개의 레이어에서 Embedding Propagation Layer을 통과한 임베딩 벡터에 $\alpha_{k} $를 가중합하여 최종 임베딩 벡터를 계산한다. 이러한 Layer Combination은 다음 3가지 의미를 갖는다.
- 레이어의 수가 증가할수록, 임베딩 값이 서로 유사해지는 over-smoothing 문제를 해결할 수 있다.
- 각각의 레이어를 통과한 임베딩 벡터들은 서로 다른 의미를 가진다.
- 첫번째 레이어의 임베딩 : 유저와 아이템의 smoothness
- 두번째 레이어의 임베딩 : 유저와 다른 유저가 연결된 아이템 및 유저(overlap item, overlap user)의 smoothness
- 세번째 레이어의 임베딩 : 고차 연결성 구조
- 등등
- 가중치 $\alpha_{k}$를 통해 self-connection 효과를 갖는다.
3-1-3. Matrix Form
LightGCN의 수행과정을 행렬 형태로 보고자 한다.
먼저 user-item interaction matrix를 $R\in \mathbb{R}^{M\times N}$로 표현할 수 있으며, 이때 $M$은 유저의 수, $N$은 아이템의 수를 의미한다.
이를 사용하여 인접행렬로 표현하면, $A=\begin{bmatrix} 0 & R \\ R^{T} & 0 \\ \end{bmatrix}$로 표현할 수 있다.
※ 인접행렬 : 행과 열이 연결성을 의미하며, 자기 자신을 연결하는 대각성분을 기준 대칭행렬
GCN의 구조인 $H^{(l+1)}=\sigma (AH^{(l)}W^{(l)})$와 같이 LightGCN에서는 $E^{(k+1)}=AE^{(k)}$ 형태가 된다. 인접행렬 $A$는 Graph Laplacian Matrix이므로, $E^{(k+1)}=(D^{-\frac{1}{2}}AD^{-\frac{1}{2}})E^{(k)}$가 된다. 이때, $D$는 $(M+N)\times (M+N)$ 크기의 대각 차수 행렬(diagonal degree matrix)를 의미한다.
최종적으로는 다음과 같은 행렬표현이 된다.
최종 임베딩 매트릭스는 초기 임베딩 $E^{(0)}$이 고정되고, $\tilde{A}$를 $K$ 제곱 형태로 변환하여 연산의 효율성이 증가했음을 확인할 수 있다.
3-2. Model Analysis
논문에서는 LightGCN이 불필요한 요소를 제거한 가벼운 모델뿐만 아니라 다음 3가지 측면에서 합리성을 입증했다.
(1) identity matrix($I$)를 인접행렬($A$)에 더함으로써 self-connection효과를 가질 수 있다.
이는 "SImplifying Graph Convolutional Networks"에서 입증되었다. 이때, $(D^{-\frac{1}{2}}+I)^{-\frac{1}{2}}$항의 역구, 임베딩 값들을 재조정하는 역할만 하게 되므로 생략한다. k번째 임베딩 매트릭스를 구하는 식을 이항정리를 통해 풀어서 쓸수 있으며, 각 LightGCN 레이어의 가중합 식과 동일하다.
※ 이항정리 : n이 자연수일 때, $(a+b)^{n}=_{n}C_0a^n+_{n}C_1a^{n-1}b+_{n}C_2a^{n-2}b^2+\cdots +_{n}C_{n}b^{n}$
(2) LightGCN은 over-smoothing 문제를 잘 다룰 수 있다.
이는 "Predict then propagate: Graph Neural Networks meet personalized pagerank(APPNP)"에서 입증되었다. over-smoothing이란 GNN이나 CNN 기반 모델에서 레이어의 수가 증가할수록 최종 임베딩 값이 유사해짐으로써 모델의 성능저하를 야기하는 문제이다. 이러한 문제를 해결하기 위해서 k+1번째 임베딩 $E^{(k+1)}$을 구하는 수식에 초기 임베딩 값 $E^{(0)}$을 더해준다. 아래의 수식을 LightGCN의 over-smoothing control 수식이다.
이때의 $\beta $를 통해 초기 임베딩 값의 영향력을 조정할 수 있다.
(3) 유저(아이템)과 연결된 다른 유저(아이템)의 second-order layer를 분석하여, 해당 관계의 smoothness를 구할 수 있다.
아래의 수식은 유저 측면에서 2-layer smoothness를 표현한 것이다. 유저와 다른 유저들간의 공통으로 연결된 아이템으로부터 smoothness의 강도를 나타내는 coefficient를 구할 수 있다.
위의 식으로부터 다음과 같은 관계를 알 수 있다.
- 상호작용이 많은 아이템의 수가 많을수록, coefficient는 커진다.
- 해당 아이템의 연결이 적을수록 coefficient는 커진다.
- 유저 u와 연결된 유저 v가 적을수록 coefficient가 커진다.
3-3. Model Training
위의 결과를 종합할 때, LightGCN의 trainable parameters는 유저와 아이템 각각의 초기 임베딩 값이 사용된다는 것을 알 수 있다. 이후 모든 유저에 대해서 실제 구매한 아이템과 구매하지 않은 아이템의 차이를 계산하여 실제 구매한 아이템에는 높은 가중치를 부여하고 구매하지 않은 아이템에는 낮은 가중치를 부여해 loss를 계산하는 BPR loss( Baysian Personalization Rank loss )를 사용하여 모델을 최적화한다.
4. Experiments
실험은 NGCF와 같은 데이터를 사용했다. 단, Yelp2018 데이터의 경우 개정된 버전을 사용했기에 약간의 차이가 있다고 한다.
먼저, NGCF와의 성능 비교 결과는 다음과 같다.
표를 보면, Recall과 NDCG를 지표로 보았을 때 모든 데이터셋과 레이어의 수에서 LightGCN의 성능이 매우 우수했다. 또한 training loss 그래프를 보면 LightGCN의 loss가 더 낮음을 볼 수 있으며, 보다 적은 epoch에서 Recall 성능이 높게 나온다는 것을 알 수 있다.
SOTA 모델들과의 성능비교는 다음과 같다.
이때도 LightGCN의 성능이 우수한 것을 알수 있다.
Layer Combination의 효과에 대한 실험은 다음과 같다.
위 그래프에서 LightGCN은 Layer Combination을 적용한 모델이고, LightGCN-single은 적용하지 않고 각각의 k번째 임베딩 레이어를 사용한 모델이다.
먼저, LightGCN-single을 보면 레이어 수가 많아질수록 성능이 저하되는 것으로 보아, over-smoothness가 발생했다고 볼 수 있다. 반면, LightGCN의 경우는 레이어가 많아질수록 성능이 향상됨을 볼 수 있다.
위의 결과를 통해서 Layer Combination이 over-smoothness 문제를 효과적으로 완화 또는 해결했다고 판단할 수 있다. 단, 논문의 저자들이 $\alpha$를 $\frac{1}{k+1}$로 uniform하게 설정하였기 때문에, over-smoothing이 발생한 LightGCN모델이 Amazon-Book 데이터셋에 대해서 성능이 높게 측정되었다. 논문의 저자들은 이에대해 적절한 하이퍼파라미터 튜닝을 통해 해결될 수 있는 문제라고 말했다.
5. Conclusion
결론적으로, GCN의 모델 구조를 CF에 사용하기에는 복잡하고 불필요한 요소가 많으므로, 이를 ablation study를 통해 제거하여 추천이라는 목적에 맞게 구성할 필요가 있었다. 추천의 성능을 저하시켰던 feature transformation과 non-linear activation을 제거하고 neighborhood aggregation과 Layer Combination을 사용한 LightGCn 모델을 제안하였다.
LightGCN은 모델의 Embedding Propagation 과정에서 첫번째 임베딩인 $E^{(0)}$만을 학습 파라미터로 사용함으로써 가볍고 효율적인 연산이 가능하고, 유저와 아이템의 스코어를 계산하기 위한 prediction layer에서 Layer Combination을 통해 self-connection 효과를 가짐으로써 over-smoothing 문제 또한 해결할 수 있었다.
참고 1)
https://pongdangstory.tistory.com/513
라플라시안 메트릭스 / Laplacian Matrix
Graph 기반의 Collaborative Filtering의 논문을 읽다가, Graph Laplacian norm을 접하게 되었다. 무엇인지에 대해서 하나씩 찾아보다가, 라플라시안 메트릭스부터 차근차근히 정리하기로 했다. 먼저, 그래프
pongdangstory.tistory.com
참고 2)
https://arxiv.org/abs/2002.02126
LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation
Graph Convolution Network (GCN) has become new state-of-the-art for collaborative filtering. Nevertheless, the reasons of its effectiveness for recommendation are not well understood. Existing work that adapts GCN to recommendation lacks thorough ablation
arxiv.org
참고 3)
https://arxiv.org/abs/1905.08108
Neural Graph Collaborative Filtering
Learning vector representations (aka. embeddings) of users and items lies at the core of modern recommender systems. Ranging from early matrix factorization to recently emerged deep learning based methods, existing efforts typically obtain a user's (or an
arxiv.org
'DS | Data Science > 논문 리뷰' 카테고리의 다른 글
| [논문] Item-based collaborative filtering recommendation algorithms (0) | 2022.10.20 |
|---|---|
| [논문] BPR: Bayesian Personalized Ranking from Implicit Feedback (1) | 2022.10.13 |
| [논문] Collaborative Filtering for Implicit Feedback Datasets (0) | 2022.10.06 |