[논문 리뷰] Neural Graph Collaborative Filtering

논문 : https://arxiv.org/abs/1905.08108

오역, 오류는 댓글로 말씀 부탁드립니다!

---

문제 상황 : Collaborative signal capture

기존 모델

• 가정 : 유사한 사용자는 특정 상품에 대해 유사한 선호도를 보일 것
• 과정
  1. embedding : 상호작용을 재구축하기 위해 user, item을 파라미터화  
     
     • 파라미터를 기반으로 선호도 예측
     • 이미 존재하는 feature로부터 mapping하는 방법
       • 단점 : 충분하지 않은 collaborative signal
  2. 상호작용 모델링 : embedding 기반으로 과거 상호작용 재구축
• 단점 : 주요 collaborative signal을 명시적으로 인코딩하지 않음
  (= 상호작용을 고려하지 않음)
  • collaborative signal : user(item) 간 유사성을 나타내는 상호작용 내 잠재 요인
  • embedding의 부족함을 채우기 위해 상호작용 함수에 의존하게 된다
  • 그러나 실제로는 대규모 상호작용이 일어나기 때문에 원하는 collaborative signal을 추출하기 어려움

high-order connectivity의 중요성

• user-item interaction graph : 사용자와 아이템의 상호작용
  • node : user, item
  • edge : 상호작용
  • u1 : target user, 추천받는 사용자
• high-order connectivity : l > 1인 경로. semantic이 풍부하다
  • l=1 인 범위에는 user1과 직접적으로 상호작용한 item1, 2, 3가 포함되어 있다
  • l=2인 범위에는 user1과 구매한 아이템이 겹치는 user2,3가 포함되어 있다
    • user2 : item2 공통으로 구매
    • user3 : item3 공통으로 구매
  • l=3인 범위에는 user2,3이 구매한 item 4,5가 포함되어 있다
  • 1번(빨간색) : user1과 user2의 유사성이 높다는 것을 보여준다
  • item4는 1번과 3번으로 user1과 연결되어 있지만, item5는 2번으로 user1과 연결되어 있다
    • item5보다 item4를 선호할 확률이 높음

기존의 해결 방법

• high-order connectivity
  • train data 보강에만 활용 & 예측은 MF로 실시
  • 논문에서는 high-order connectivity를 예측 모델에 연결하여 활용
• Conventional graph CNN
  • item embedding의 contribution만 고려
  • 논문에서는 element-wise product로 item-user 간 상호작용을 message에 인코딩

기존 연구

Model base CF methods

• CF에 최적이 아닌 embedding 함수 사용
  • 명시적으로 CF signal을 인코딩하지 못함
  • 적절한 embedding을 얻기 어려움
  • 간접적으로 연결된 user, item이 embedding 공간에서 가까워진다고 보장할 수 없다

Graph base CF methods

• high-order connectivity fully explore (X)
  • high-order connectivity가 embedding 함수에 직접 주입되지 않는다
  • high-order connectivity가 훈련 data 보강에만 활용

Graph Convolutional Networks

• GC-MC : 하나의 합성곱 layer만 사용
  • high-order connectivity의 collaborative signal capture 불가
• Pinsage : item과 item을 graph로 표현
  • 사용자 행동보다 item 관련 level을 capture 하는 데 집중
• SpectralCF : user와 item 간 모든 연관성을 발견하기 위해 spectral 합성곱을 사용
  • graph 인접 행렬의 고유값 분해를 통해 user, item 간 연결성을 발견
  • 결과 : 연산비용 증가

 

NGCF

요약

• 양방향 그래프 구조를 이용하여 user-item 간 상호작용 통합
  • 효과 : high-order connectivity 모델링. 명시적인 방법으로 임베딩 과정에 collaborative signal 주입
• high order connectivity 활용 : 예측 모델에 연결
  • 상호작용 graph 구조에 collaborative signal 인코딩
  • 효과 : embedding 개선
• 신경망 형식 graph 사용
  • tree 형식의 graph는 적용이 어려움
  • layer 개수가 많아질수록 강한 information flow capture
    • information flow : 추천 우선순위 결정

모델 구조

• embedding layer : embedding 초기화
  • user-item interaction graph에 embedding을 전파, 연산
  • 명시적으로 embedding에 collaborative signal 주입
  • 효과 : embedding 효율성 개선
• embedding propagation layer : 상호작용하는 item 및 user 집계
  • 여러 개를 stack : high-order connectivity의 collaborative signal capture
  • GNN의 message passing 구조
    • graph 구조를 따라 CF signal을 포착하고 embedding을 개선하기 위함
  • item을 구매한 사용자 : item의 feature
    • 아이템 간 collaborative 유사도 측정 시 사용 가능
  • 가정 : 상호작용 = 선호도
  • 장점 : 명시적으로 1차원 연결성 정보를 사용하여 user, item representation 간 연관
  • First order Propagation(l = 1)
    1. message construction : item - user 간 상호작용을 message에 인코딩 by element-wise product
       1. message
          • 사용자, 아이템 embedding 간 affinity에 의존
          • discount factor : 과거 item이 사용자 선호도에 얼마나 기여하는지 경로 길이에 따라 감소하는 전파 메시지
       2. 효과 : represent 및 추천 능력 개선
    2. message aggregation : representation 개선을 위해 이웃 user로부터 전파된 message 집계
       1. aggregation function : leakyrelu 사용
          • LeakyReLU : 긍정 signal, 적은 부정 signal에 모두 encode 가능
       2. 연결된 user로부터 전파된 정보를 통해 item에 대한 representation 확보 가능
  • High-order Propagation(l > 1) 
    1. stack된 embedding propagation layer : high-order connectivity 정보 이용
       • high order connectivity : user, item 간 연관성 점수를 계산하기 위한 collaborative signal 인코딩에 중요
       • stack의 효과
         • 이웃에서 전파된 메시지 수신 가능
         • representation 학습 과정에 collaborative signal 주입
    2. matrix form propagation rule : embedding 전파를 종합적으로 보여주고 batch 구현을 용이하게 하기 위함
       • 효율적으로 모든 user, item의 representation 즉시 update 가능
       • node 샘플링 과정 생략 가능

stack된 embedding propagation layer를 통해 collaborative signal이 capture된다

• Prediction layer
  • propagation을 통해 item 및 사용자에 대한 다양한 representation 확보
    • 다양한 representation : 사용자 선호도를 반영하는 기여도의 차이
    • concat한 representation : 사용자에 대한 최종 embedding
      • concat : 추가로 학습시킬 파라미터가 없기 때문에 다른 집계 방식보다 간단
        • 내적으로 target item에 대한 특정 user 선호 계산
    • 전파 범위 조정 by 초기 embedding 보강 및 L 조정
• Optimization
  • pairwise BPR loss 사용
    • BPR : 관측된 상호작용과 미관측된 상호작용 간의 상대적인 순서를 고려한다
      • 관측된 상호작용이 선호도를 더 잘 나타내기 때문에 큰 예측값을 가짐
  • model size
    • 파라미터 추가로 인해 발생하는 비용이 적다
      • high-order connectivity 모델링을 위해 추가되는 파라미터가 적다
  • Message and Node dropout : overfitting 문제를 해결하기 위함
    • message dropout : representation이 user-item 간 단일 연결 여부에 대해 robust하게 함
    • node dropout : 특정 사용자, item의 영향을 줄임
• SVD++과 NGCF
  • NGCF : 일반화된 SVD++ 모델
    • SVD++ : 고차원 propagation layer가 없는 NGCF
  • NGCF를 SVD++로 바꾸기 위한 방법
    
    • propagation layer : 변형 매트릭스, 비선형 활성화함수를 사용하지 않음
    • L = 1
    • 결과 : 사용자, item embedding을 최종 representation으로 사용

 

Experiment

baseline 모델

• MF
• GC-MC
• NeuMF : SOTA를 달성한 신경망 모델
• CMN : SOTA를 달성한 메모리 기반의 CF
• Hop-Rec : SOTA를 달성한 graph 기반의 CF
• Pinsage : user-item 상호작용을 graph에 적용

NGCF와 SOTA CF 방법의 성능 비교 : high-order connectivity의 효과

• overall comparison
  • MF, NeuMF : embedding 학습 과정에서 명시적으로 high-order connectivity을 모델링하지 않기 때문 
    • MF : 낮은 성능
      • 내적만으로 복잡한 상호작용을 표현하기 어려움
    • NeuMF : MF보다 좋은 성능
      • 비선형 feature 상호작용 capture
  • GC-MC
    • MF, NeuMF보다 좋은 성능 : 1차 이웃 통합으로 representation 학습을 개선하기 때문
    • 일부 데이터에서 NeuMF보다 낮은 성능 : 비선형 feature 상호작용을 fully explore하지 않기 때문
  • CMN
    • GC-MC보다 좋은 성능 : 신경망 attention 매커니즘으로 인해 user마다 다른 가중치를 가지게 되기 때문
  • Pinsage, Hop-Rec : 높은 성능
    • high-order connectivity 및 고차원 이웃 모델링을 하기 때문
  • NGCF : 가장 높은 성능
    • embedding 함수에 collaborative signal을 capture하는 것의 중요성
    • 각 propagation layer가 각기 다른 정보를 encoding함
    • 명시적 인코딩을 통해 representation 개선

high-order connectivity

high-order connectivity

• Performance Comparision : high-order connectivity 정보 사용 시 sparsity 문제가 완화되는지 확인하기 위함
  • 모든 데이터에서 NGCF가 가장 높은 성능
    • high-order connectivity 정보 사용 시 inactive 사용자의 representation 학습 가능
  • 많은 user가 포함될수록 성능 향상
    • embedidng propagation : 상대적으로 inactive 사용자에게 효과 좋음

Embedding propagation layer의 영향

layer 개수의 영향

• embedding propagtion layer가 많아질수록 성능이 개선된다
  • 2차, 3차 연결성이 collaborative 사용자 유사도와 signal capture에 효과적
• propagation layer stack : 4개 이상 stack 시 overfitting으로 성능 저하
  • 최적의 layer 개수는 3개
• propagation layer 개수에 상관없이 NGCF가 좋은 성능을 보임

propagation layer와 layer 집계 방법(NGCF, SVD++ 등)의 영향

• NGCF의 성능 향상 : 다른 layer는 선형 변환만 사용하기 때문
• SVD++ 성능 하락 : 비선형 변환, node 자신과의 message의 중요성을 보여줌
• 같은 layer를 사용해도 NGCF 방식으로 output concat 시 성능 개선
  • layer 집계 방법의 중요성

Dropout의 영향

• node dropout 성능 > message dropout 성능
  • 특정 user-item 쌍에 대한 모든 message dropout은 representation을 특정 edge, node의 영향에 robust하게 만든다
  • node dropout : GNN 과적합에 효과적인 전략

epoch에 따른 성능

• NGCF : 빠른 수렴
  • 높은 model capacity로 인해 embedding propagation 효율이 높음

high-order connectivity이 representation 학습에 미치는 영향

= representation이 NGCF 깊이에 어떤 영향을 받는가

• MF와 NGCF를 차원축소(t-SNE)한 결과 비교
  • NGCF : user-item 간 거리가 가깝고 군집화가 잘 되어 있음
    • 연결성에 user-item 간 관계가 잘 반영됨
  • embedding propagation layer stack 시 : 과거 item의 embedding이 가까워짐
    • propagation layer : representation에 collaborative signal을 명시적으로 주입하기 때문

 

Conclusion

• 명시적으로 모델 기반 CF의 embedding 함수에 collaborative signal 통합
• user-item 통합 graph에서 high-order connectivity 이용
  • embedding propagation layer : user-item embedding 상호작용을 collaborative signal로 변환
  • embedding 학습 과정에 user, item 그래프 구조 주입 시 성능 개선