[논문 리뷰] LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation

 

출처:https://arxiv.org/abs/2002.02126

LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation

 

 

 

ABSTACT

 

GCN은 collaborative filtering의 최첨단 기술로 사용되지만, 비효율적인 성능에 문제점이 있다.

그 이유는 GCN은 본래 그래프 분류에 특화되어 있기 때문이다.

논문의 저자들은 GCN의 디자인에서 성능 저하를 발생시키는 부분(feature transformation and nonlinear activation)을 찾았고,

추천을 위한 필수적인 부분만을 포함시킨 LightGCN을 만들었다.

 

이는 기존의 동일한 환경의 Neural Graph Collaborative Filtering(NGCF) 보다 평균 16.0%의 발전을 보였다.

 

 

 

 

PRELIMINARIES

 

일단 NGCF에 대해 요약해 보자.

 

i는 item, u는 user를 의미하한다.

논문에서는 NGCF의 각 층에서 계산되는 feature transformation and nonlinear activation가 성능의 저하를 일으키면서, CF에는 도움이 되지 않는다고 밝히고 있다.

 

이러한 임베딩은 propagation에 의해 진행되고 있지만, 중요한 것은 embedding의 quality이다.

따라서 기존의 concatenation 방식에서 sum 방식으로 변경하면 약간의 성능 개선이 이뤄진다.

concatenation

sum

 

성능에 영향을 미치는 두 가지 요소를 지웠을 때의 성능 개선도 이루어졌다.

 

그래프를 확인해보면 feature transformation와 nonlinear activation를 모두 제거한 NGCF-fn은 상당한 성능 향상을 보이고 있다.

 

가중치 메트릭스 W를 제거하고 identity Matrix를 삽입한 NGCF-f 마저도 NGCF 보다 좋은 성능을 내고 있다.

즉, 두 가지 요소는 성능을 떨어뜨리는 데도 식에 포함되어, 학습의 복잡도를 올리고 있다.

 

 

METHOD

 

1. LightGCN

 

이제 LightGCN의 디자인에 대해서 논한다.

target node u를 계산하기 위해서 u의 이웃인 item node들과 자신의 이전 layer에서의 embedding을 aggregate 한다.

AGG는 aggregation function으로 k-th layer의 정보를 집약한다.

 

AGG는 다양하게 튜닝이 가능하다.

예를 들어 이전 글에서 살펴본 GraphSAGE는 AGG로 LSTM을 사용했다.

다양한 AGG 방법들은 대부분 feature transformation와 nonlinear activation를 진행시킨다.

물론, 일반적인 graph classification에서는 잘 동작하지만, CF에서는 그렇지 않다.

 

 

 

Light Graph Convolution 구조는 아래의 3가지를 제거하였다.

1. self-connection

2. feature transformation

3. nonlinear activation

 

이 구조에서는 단순히 wighted sum aggregation 방식을 채택하였다.

 

 

출처: https://medium.com/stanford-cs224w/lightgcn-for-movie-recommendation-eb6d112f1e8

 

 

 

 

이제 operation은 아래와 같이 표현된다.

user node인 u의 k+1 th layer는, 자기 자신도 제외하고 이웃 item 노드들만을 sum 하여 결정된다.

빨간 밑줄을 그은 부분이 graph convolution operation의 embedding이 계속 증가하는 것을 방지하는, normalization의 역할을 하게 된다. L1 norm의 방식을 채택할 수도 있지만, 이 normalization이 더 효과적인 것으로 판단되었다.

 

 

이러한 방식을 K번째 layer까지 반복되면, 노드마다 0~K th의 embedding 값이 생성된다.

우리는 최종적인 출력 값을 이 모든 embedding 값을 더해주어 생성한다.

여기서 사용되는 a는 hyper-parameter(사용자가 직접 세팅하는 값)로, 굉장히 중요한 값이다.

 

논문에서는 a(k)의 값을 1/(K+1)을 사용하였을 때 좋은 결과를 냈다고 설명한다.

추가적인 a의 튜닝은 LightGCN의 심플함을 해치므로 진행하지 않는다.

 

 

 

출처: https://medium.com/stanford-cs224w/lightgcn-for-movie-recommendation-eb6d112f1e8

 

 

 

Layer의 수가 늘어나면 over-smoothing 문제가 발생한다.

over smoothing problem

특히 CF가 다루는 bipartite graph는 user에서 item으로, item에서 user로 층이 이동하면서 노드가 쉽게 중복될 수 있다.

 

따라서 layer를 쌓기보다는 combinig 하는 방식이 더 종합적인 표현이 가능해진다.

 

 

 

최종적인 예측은 user와 item의 embedding 값을 내적해서 구할 수 있다.

이것으로 추천 목록을 만들어 낼 수 있다.

 

 

 

 

이제 LightGCN의 Matrix 형식을 살펴보자.

 

Matrix R은 usre-item 간의 interaction을 나타낸 Matrix이다.

만약 user i가 item j에 대하여 interact 했다면 R(i, j)는 1이고, 아니라면 0이다.

 

R을 transfer 하면 반대로 item이 user를 가리키는 Matrix가 되고, 이 두 가지를 결합하면 Adjaction Matrix가 나온다.

 

 

 

 

이제 각 층의 embedding 값을 다음과 같이 표현할 수 있다.

 

여기서 등장하는 것이 Sysmmetric normalized Laplacian matrix이다.

L(sym)은 대각선에는 1이, 인접 노드라면, 우리가 필요한 degree 값으로 나누는 normalization이 들어 있다.

자세한 내용은 이 게시글을 참조하자.

 

 

이제 이와 같은 수식을 완성할 수 있다.

이제 고정값을 제외하고 A만 제곱하여 값을 구할 수 있다.

 

 

 

2. Model Analysis

LightGCN은 단순히 간단해지기만 한 모델이 아니다.

 

 

2-1. self-connection

 

Simplifying graph convolutional networks(SGCN)에서 입증된 self-connection 방식을 사용한다.

Identity Matrix를 Adjaction Matrix라고 생각하면, 자기 자신을 가리키는 Matrix로 볼 수 있다.

Identity Matrix를 수식에 추가함으로써 self connection을 추가시킬 수 있다.

SGCN

이로써 self-connection의 값도 각 LGC layer에 반영된다.

 

 

2-2. over-smoothing problem

 

over-smoothing problem의 해결은 Predict then propagate: Graph neural networks meet personalized pagerank(APPNP)에서의 방식에서 입증되었다.

Layer가 증가할수록 모든 노드의 임베딩 값이 유사해지는 것을 각 층의 임베딩 영향력을, Beta로 조정해주는 것으로 해결한다.

 

in APPNP

LightGCN에 적용

 

 

2-3. Second-Order Embedding Smoothness

 

층이 두 개인 LigthGCN을 생각해 보자.

 

최종적으로 user 노드의 embedding을 구하면, 이전 층은 item 노드들, 그 이전 층은 user 노드들이었을 것이다.

 

밑줄을 친user와 최종 user 간의 사이의 공통된 item 노드를 통해 coefficient를 구할 수 있다.

 

user v들과 최종 유저 u의 연결이 적을수록  coefficient가 커지고,

서로 공통된 item이 많을수록 coefficient는 커지고,

해당 item들이 degree(상호작용)가 적을수록 coefficient는 커진다.,

 

 

Model Training

LightGCN에서는 가중치 Matrix가 없으므로, 학습가능한 parameter는 첫 layer의 input embedding이다.

 

학습을 위한 loss function은 Bayesian Personalized Ranking (BPR) loss를 사용한다.

유저의 수를 M이라고 하고, i는 실제로 구매한 item들, j는 구매하지 않은 아이템들이라고 했을 때,

예측된 i의 구매 확률과 j를 구매하지 않을 확률의 차이를 계산한다.

 

이를 통해 실제 구매한 item i들에게 높은 가중치, 구매하지 않은 아이템 j들에게는 낮은 가중치를 부여한다.

L2 reguralization은 overfitting을 방지하기 위해 사용된다.

 

이제부터 위의 데이터를 이용해 테스트를 진행할 것이다.

 

 

 

 

 

EXPERIMENTS

 

NGCF와 동일한 환경과 데이터를 사용해 실험해본 결과는 다음과 같다.

그래프를 보면 알 수 있듯이, LightGCN이 NGCF보다 성능도 우수하고, 수렴도 빠르게 이루어진다.

즉, 속도면에서도 우수하다.

 

 

 

이번에는 layer들을 combination 하지 않는 LightGCN-single 방법과 비교해 보자.

 

 

Gowalla dataset에서는 layer가 증가할수록 LightGCN이 좋은 성능을 내지만, Amazon-Book dataset에서는 그렇지 않다.

이는 Amazon-Book dataset에서 더 많은 over-smoothing 이 일어난 것이다.

 

 

 

참고:

https://leehyejin91.github.io/post-bpr/

https://medium.com/stanford-cs224w/lightgcn-for-movie-recommendation-eb6d112f1e8

 

자료: http://web.stanford.edu/class/cs224w/index.html

 

 

구현 코드:

https://github.com/kuandeng/LightGCN

GitHub - kuandeng/LightGCN

 

 

https://github.com/microsoft/recommenders/blob/main/examples/02_model_collaborative_filtering/lightgcn_deep_dive.ipynb

GitHub - microsoft/recommenders: Best Practices on Recommendation Systems