오늘은 오랜만에 추천시스템 알고리즘 중 LightGCN 논문에 대해 리뷰해보려고 한다.
대표적인 추천시스템 알고리즘 중 하나로 GCN의 common design인 1) feature transformation, 2)nonlinear activation을 없애고 성능을 올린 알고리즘이다.
Abstract
추천시스템 Collaborative Filtering에서 Graph Convolution Network(GCN)은 새로운 SOTA가 되었다.(2020년 당시 얘기임)
근데 GCN의 효율성은 잘 입증이 안되었는데, GCN 사용한 작업들도 GCN에 대해서 ablation 분석(GCN에서 몇가지 특성 빼가면서 분석하는 것)도 안하고 사용했기 때문이다.
※원래는 GCN 자체가 graph classification task에 맞춰서 나왔기 때문에 ablation 분석을 해보면서 사용해야함.
→ 이 논문에서는 GCN의 두 common design인 feature transformation, nonlinear activation이 Collaborative Filtering 성능에 그리 좋은 영향을 끼치지 못한다는 걸 발견했다. 심지어, 더 악화시킬 수도 있다는 걸 발견했다.
저자들은 GCN의 design을 단순화해서 더 추천에 정확하도록 만들었는데, 말그대로 Light하게 만들었음으로 이름을 "LightGCN"으로 지었다. 위에서 말한대로 별필요없는 feature transformation, nonlinear activation은 빼고 GCN에서 필수적인 요소(neighborhood aggregation)만 가지고 만들었다.
상세하게 말하자면, LightGCN은 user, item embeddings을 user-item interaction graph에서 선형적으로 propagation함으로써 학습하고 모든 레이어에서 학습된 embedding을 weighted sum해서 final embedding으로 사용한다.
Introduction
Collaborative Filtering에서 가장 common 패러다임은 user와 item을 적절하게 표현할 수 있는 latent features(=embedding)을 찾는 것이다. Matrix Factorization은 초기 모델로 user의 ID를 embedding으로 project시키는 것이다. 후에는, user ID를 기존 interation history와 쌓아서 input으로 만드는데, SVD++와 같은 모델이 이러한 방식을 쓴다.
User-item interaction graph의 시각에서 이러한 개선들은 user의 subgraph(더 자세히 말하자면, 유저의 one-hot neighbors)를 사용하는 것으로 이해할 수 있다.
High-hop neighbors의 subgraph structure을 더욱 사용해서 NGCF가 나오게 됐는데, 기존 CF에서 SOTA 성능을 보여줬다.
NGCF는 feature transformation, neighborhood aggregation 그리고 nonlinear activation을 사용해서 embedding을 정의했다. (GCN을 바로 사용해버려서 너무 heavy하고 burdensome)
→ 결과적으로 CF task에 맞지않았다.(Abstract에서도 말했듯이, GCN은 원래 graph에서 node classification하려고 나온것)
ㅇ node classification task의 graph에서 node : 각 node가 풍부한 특성 가지고 있음.
ㅇ user-item interaction graph에서 node : 각 node가 one-hot ID로만 묘사되어 있음.(딱히 중요한 특성X)
이러한 생각때문에, 저자들은 NGCF에 대해 ablation study를 진행했고 결론을 내렸다.
two operations inherited from GCN — feature transformation and
nonlinear activation — has no contribution on NGCF’s effectiveness
요악하자면 이 논문의 Main Contributions은 아래와 같다.
- GCN의 two common designs(feature transformation, nonlinear activation)은 CF의 효율성에서 긍정적인 효과가 전혀 없음.
- 따라서, LightGCN을 제안했는데, GCN에서 필수적인 부분인 neighborhood aggregation부분만 포함한 디자인이다.
- LightGCN을 기존의 NGCF와 같은 조건하에서 비교해보았다.(더 좋게 나옴)
Preliminaries
계속해서 언급했듯이, LightGCN은 GCN에서 Feature Transformation과 Nonlinear Activation을 제거했는데 이 두가지에 대해 우선 알아보자.
1. NGCF Brief
처음에 각 user와 item은 ID embedding과 연결되어있는데, 아래와 같이 정의해보자.
그러면 NGCF는 user-item interaction graph를 embedding을 propagate하려고 사용하는데, 다음과 같다.
(위 index가 k인건 k layers propagation후에 user, item embedding을 뜻한다.)
L개의 layers를 propagate함으로써, NGCF는 아래와 같이 user u에 대한 L+1개의 embeddings을 얻게 된다.
그리고 item i에 대한 L+1개의 embeddings을 얻게된다.
그런다음, 이 L+1개의 embeddings을 쌓아서 final user embeddings, item embeddings을 얻는다.
(prediction score를 얻기위해 inner product사용)
NGCF는 standard GCN을 따라 nonlinear activation과 feature transformation matrices W1, W2를 사용한다. 그러나 이 두 operation(nonlinear activation, feature transformation)은 CF에 유용하지 않다.
※ semi-supervised node classification에서는 각 node가 풍부한 특성을 가지고 있음.ex) 논문의 title나 abstract word
→ nonlinear transformation을 여러 layer에 걸쳐 진행하면, feature learning에 도움이 됨.
2. Empirical Explorations on NGCF
이제 저자들이 진행한 NGCF ablation study에 대해 알아보자.
GCN의 핵심이 propagation함으로써 embedding을 계속해서 만들어가는 것이기때문에, same embedding size로 진행해야한다.
→ Final embedding을 만드는 방식을 바꿨는데, 기존에 그대로 쌓는 방식인 concatenation에서 sum하는 방식으로 바꾸었다.
또, NGCF의 간단화된 버전을 각각 실험해서 feature transformation과 nonlinear activation의 영향도를 체크하였는데 아래와 같다.
ㅇ NGCF-f : no feature transformation matrices W1, W2
ㅇ NGCF-n : no nonlinear activation function σ
ㅇ NGCF-fn : no feature transformation, no nonlinear activation function
(다른 hyper-parameters등은 다 똑같이 셋팅함)
위 각각 다른 버전들을 이용해서 실험한 결과, NGCF-f는 기존 NGCF보다 좋은 성능을 보여준반면에, NGCF-n은 성능에 그리 큰 영향을 끼치지 않았다. 하지만, NGCF-fn은 큰 성능개선을 보여준 것으로 보아, nonlinear activation만 제거하는 것은 그리 영향이 없으며 feature transformation과 함께 제거해야 성능개선이 있음을 알 수 있다.
(1) Adding feature transformation imposes negative effect on
NGCF, since removing it in both models of NGCF and NGCF-n
improves the performance significantly;
(2) Adding nonlinear activation affects slightly when feature
transformation is included, but it imposes negative effect when
feature transformation is disabled.
(3) As a whole, feature transformation and nonlinear activation
impose rather negative effect on NGCF, since by removing them
simultaneously, NGCF-fn demonstrates large improvements over
NGCF (9.57% relative improvement on recall).
위의 실험결과로 미루어보아, NGCF의 성능저하는 overfitting보다는 학습하기 어려운 것에 있다고 할 수 있다.
Method
이전까지 GCN을 간단하게 만드려는 과정에 대해 보여줬는데, 간단하게 만드는 것에 대한 장점은 다양하다.
- 더 해석가능함, 학습이 용이함, 모델 행동분석이 쉬움, 더 효과적인 방향으로 만들기 쉬움 등
이제 LightCGN에 대해 알아보자.
1. LightGCN
GCN의 기본적인 아이디어는 feature smoothing을 통해 node의 representation에 대해 학습하는 것이다.
이를 위해서 계속해서 iterative하게 graph convolution을 진행하게 된다. 즉, 아래식과 같이 neighbors의 features를 aggregation하여 새로운 representation을 만든다.
AGG는 aggreagation function으로 graph convolution의 핵심이다. AGG는 target node의 k번째 layers의 representation과 이것의 neighbor nodes를 고려한다.
1.1 Light Graph Convolution(LGC)
LightGCN에서는 간단한 weighted sum aggregator를 사용하고 feature transformation과 nonlinear activation을 사용하지 않는데, graph convolution operation(a.k.a. propagation rule)은 다음과 같다.
normalization term(아래식)은 기존의 GCN의 디자인을 따르는데, 이 term을 통해 embedding의 스케일이 graph convolution을 함에따라 계속해서 증가하는 것을 막을 수 있다.
LGC에서는 connected neighbors만 aggregate하며 target node자체는 integrate하지 않는다. 이는 기존의 graph convolution형태와 다른데, 기존에는 extended neighbors를 aggregate하며 self-connection도 해야했기 때문이다.
(다음에 나올 layer combination이 self-connection의 역할을 했기 때문에 self-connection이 필요없었다.)
1.2 Layer combination and Model Prediction
LightGCN에서 trainable한 model parameter는 0번째 layer의 embedding뿐인데, 즉 아래와 같다.
(iterative하게 다음 layer의 parameter는 계산되므로)
K layers LGC후에는, embedding을 결합하여 한 user의 final representation이 나오게 된다.
여기서 weight는 k번째 layer embedding의 중요도를 뜻하는데, hyper parameter처럼 취급될 수도 있고, model parameter로 다뤄질 수도 있다.(attention network의 output) -> 이 부분은 좀 더 알아봐야할듯.
(이 논문에서는 이 weight를 1/(K+1)로 설정했는데, 일반적으로 잘된다고 한다.)
Final representation을 얻기위해 layer combination을 하는 이유는 세가지가 있다.
(1) Layer의 수가 늘어남에따라, embeddings은 over-smoothed.
-> 그냥 마지막 layer만쓰면 너무 정보가 없음
(2) 다른 layer의 embedding은 다른 semantics을 갖고있다.
e.g. 첫번째 layer는 interaction이 있는 user-item을 smooth하게 만들고 두번째 layer는 겹치는 item이나 users가 있는 user-item을 smooth하게 만든다. 더 고차원의 layer는 더 high-hop user-item을 smooth하게 만든다.
따라서, 이런 여러 layer를 결합하여 만들면 representation을 더 정보를 많이 갖게 만들 수 있다.
(3) 각 다른 layer에서의 embedding을 weighted sum으로 결합하는 것은 self-connection의 효과가 있다.
(GCN에서는 중요한 trick임)
이렇게 final representation을 얻고 나면 inner product를 통해 ranking score를 얻게 된다.
정리하자면, (embedding iteratively학습 → weighted sum으로 final representation 얻음 → inner product로 ranking score계산)
1.3 Matrix Form
저자들은 좀 더 쉽게 실행하고 다른 기존 모델들과 비교하기 위해 LightGCN의 행렬형태도 제공한다.
User-item interaction matrix를 MXN 크기의 행렬 R이라 해보자.
(M : user의 수, N : item의 수)
행렬 R의 (u,i)위치의 element는 user u가 item i와 interation이 있으면 1, 아니면 0이라고 해보자.
그러면 user-item graph의 adjacency matrix는 다음과 같다.
0번째 layer embedding matrix를 다음 matrix라 해보자.
여기서 T는 embedding size를 뜻한다. 그럼 LGC는 아래와 같이 표현할 수 있다.
마침내, final embedding matrix는 다음과 같이 표현된다.
2. Model Analysis
LightGCN의 디자인이 간단하게 잘된다는 것을 보이기위해 model analysis를 진행하였는데, 아래의 세가지의 형태로 분석해보았다.
1) Simplified GCN(SGCN)
첫번째로는 Simplified GCN(SGCN)와의 connection에 대해 생각해보았다.
SGCN은 linear GCN model로 self-connection을 graph convolution에 결합한 것이다.
Layer combination을 함으로써, LightGCN는 self-connection의 효과를 갖게되므로 LightGCN에 self-connection을 추가할 필요가 없다.
SGCN은 nonlinearity를 제거하고 여러 weight matrics를 하나의 weight matrix로 만듦으로써 GCN를 간단히 만든것인데,
SGCN의 graph convolution은 다음과 같이 정의된다.
( (D+I)가 들어간 term은 단순히 scaling을 위해 추가한것이므로 앞으로 생략 )
SGCN에서 마지막 layer에서의 embedding은 downstream prediction task에 사용되며 다음과 같이 표현될 수 있다.
위의 식을 통해, A에 self-connection을 넣고 embedding을 propagating하는 것은 각 LGC layer에서 propagated된 embedding을 weighted sum하는 것과 같다.
2) Approximate Personalized Propagation of Neural Predictions(APPNP)
다음으로는 APPNP와 비교해보았다. APPNP는 GCN의 변형으로 Personalized PageRank에서 영감을 받아 oversmoothing을 해결하였다. APPNP는 각 propagation layer를 starting features로 보완했다. 이는 locality를 보존하려는 것(oversmotthing 방지)과 좀 더 큰 neighborhood의 정보를 이용하는 것과의 균형을 맞춘다.
APPNP의 propagation layer는 다음과 같이 정의된다.
APPNP에서 마지막 layer는 final prediction을 위해 사용되는데 다음과 같다.
3) second-layer LGC
second-layer LGC를 분석하여 이것이 한 user와 이 user의 second-order neighbors를 어떻게 smooth하게 만드는지를 보여준다. LightGCN의 linearity와 simplicity으로인해 어떻게 embedding을 smooth하게 만드는지 인사이트를 뽑아낼 수 있다.
이를위해 2-layer LightGCN을 분석해보자. 아래 second layer의 user embedding을 보자.
또다른 user v와 user 가 같은 item과 interact한다면, v의 u에 대한 smoothness strength는 다음의 coefficient에 의해 측정된다.
이 coefficient는 다음과 같이 해석가능하다 :
Second-order neighbor v의 u에 대한 영향은 다음 4가지에 의해 결정된다.
1) 함께 interact하는 아이템의 수 (더 많을수록 영향도가 더 크다.)
2) 함께 interact하는 아이템의 popularity (더 인기없는 아이템을 공유할수록 영향도가 더 큼. 더 유저의 개인화된 취향을 보여주기때문에)
3) user v의 activity (덜 active할수록 영향도가 더 큼. 덜 active한 user의 interaction은 소중)
LightCGN의 symmetric fomulation때문에 item측면도 위의 user측면처럼 해석이 가능하다.
3. Model Training
앞서 언급했듯이, LightGCN의 학습가능한 파라미터는 0th layer의 임베딩뿐이다.
즉, model complexity는 standard matrix factorization(MF)와 같다.
(맨처음 파라미터가지고 iteratively 다음 layer의 파라미터 결정되므로, 들어가는 연산은 MF밖에 없다.)
1) Bayesian Personalized Ranking(BPR) Loss
Loss로 Bayesian Personalized Ranking(BPR) Loss를 사용했을때, 이는 pairwise loss로 이미 관찰된 요소의 prediction이 관찰되지 않은 요소의 prediction보다 크도록 한다.
위에서 lambda는 L2 regularization의 정도를 조정한다.
2) Adam optimizer
Loss를 낮춰나가는 optimizer로는 Adam optimizer를 사용했다.(mini-batch 형태로)
다른 advanced negative sampling(hard negative sampling, adversarial sampling)을 통해 LightGCN학습을 개선시킬수도 있지만 이는 future work로 남겨두자.
GCN과 NGCF에서 흔히 사용되는 Dropout은 사용하지 않았는데, feature transformation weight matrices가 없기 때문이다.
-> L2 regularization으로 overfitting을 예방하기에 충분하다.
(참고로 NGCF는 2개의 dropout ratios를 조정해나가야한다.)
Experiments
1. Experimental Settings
1.1 Compared Methods
주된 비교대상은 NGCF인데, NGCF는 GCN-based models보다도 나은 성능을 보여줬을뿐만 아니라, factorization-based models보다도 좋은 성능을 보여줬다. NGCF에 더해 두 CF methods와도 비교했는데, 아래와 같다.
- Multi-VAE
Item-based CF method로 VAE를 기반으로 한다.Data가 multinomial distribution으로부터 생성되었다고 가정하며 parameter estimation에 variational inference를 사용한다.
- GRMF
GRMF는 graph에 Laplacian regularizer를 추가함으로써, MF를 smooth하게 만든 것이다.
똑같은 조건에서 실험하기위해 GRMF에서의 loss도 BPR loss로 변경하였다.
2. Performance Comparison with NGCF
실험을 통해 나온 main observation은 다음과 같다.
1) 모든 경우에서 LightGCN는 NGCF보다 크게 우수한 성능을 보여주었다.
특히, Gowalla dataset에서 NGCF의 최고 recall은 0.1570이며 LightGCN은 0.1830이다.
평균적으로 recall은 16.52% 더 나았으며, NDCG는 16.87% 더 나았다.
2) LightGCN은 NGCF-fn보다도 나은 성능을 보여줬다.
NGCF-fn는 NGCF에서 feature transformation, nonlinear activation을 제외한 모델인데 그럼에도 불구하고 여전히 LightGCN보다 더 많은 operation을 가지고 있다.(dropout, self-connection 등)
3) Layer의 수를 늘리는 것은 성능을 높일 수 있지만, benefits는 사라진다.
4) Training process에 따라, LightGCN의 training loss은 점점 더 낮아지는데, LightGCN이 NGCF보다 더 training data에 fit된다고 볼 수 있다.
Conclusion
이 논문에서는 CF을 위한 GCN에서 필요없는 디자인(feature transformation, nonlinear activation)을 제외시켜서 만든 LightGCN에 대해 알아보았다.
LightGCN은 두개의 필수적인 요소로 구성되어있는데 light graph convolution & layer combination이다.
Light graph convolution은 feature transformation과 nonlinear activation을 버린 형태이고, Layer combination은 node의 final embedding을 모든 layer의 embedding의 weighted sum으로 만드는 것이다.(self-connection효과가 있고, oversmoothing예방)
이러한 효과를 실험을 통해 증명해보았고 한줄로 정리하자면 LightGCN은 다음과 같다.
Easier to be trained, better generalization ability and more effective
댓글