[Paper Review] (2018, KDD) Graph Convolutional Neural Networks for Web-Scale Recommender System

4

Recommender_System

목록 보기
16/22
post-thumbnail

작성자: 이예지

Pinterest + GraphSage = PinSage

Ying, Rex, et al. Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2018. 907 citations.

Hamilton, William L., Rex Ying, and Jure Leskovec. "Inductive representation learning on large graphs." 31st Conference on Neural Information Processing Systems (NIPS 2017). 3378 citations.

해당 논문에서 제안한 모델인 PinSage에 대해 알아봅시다.

Chapter 19, CS224W

Overview

PinSage는 실제 서비스 되고 있는 핀터레스트(Pinterest)에 적용된 추천알고리즘으로, 학습에 쓰인 데이터는 pin과 board로 구성된 3 bililon 노드와 18 bilion 엣지를 가지고 있습니다.

PinSage는 GCN 모델로, 그래프 데이터에 랜덤 워크(randowm walks)와 graph convolution을 적용한 방법론입니다.

추천시스템에 적용하기 위해서는 효율적인 연산이 중요하기 때문에, GCN 모델을 서빙하기 위한 여러가지 방법을 제안하였습니다.

Introduction

당시에 GCNs(Graph Convolutional Networks)은 추천시스템을 포함한 다양한 분야에 적용되면서 많은 발전이 되었습니다. GCN의 핵심은 이웃들(neighbohoods)로부터 특징 정보를 반복적으로 모으는(aggregate) 방법을 학습하는 것입니다. 이때, convolution이라고 불리는 연산을 사용하여 one-hop 이웃들의 정보를 변형하고(transform) 모으게(aggregate) 됩니다. 이 one-hop convolution layer를 여러 개 쌓음으로써 이웃의 정보를 계속적으로 변형하고 모으기 때문에, 멀리 떨어진 이웃들의 정보까지 닿을 수 있습니다. 기존의 content based RNN 모델과는 다르게, GCN은 contents 뿐만 아니라 그래프 구조까지 활용합니다.

그러나, GCN-based 모델은 scailability가 떨어지기 때문에, 수십억 개의 노드와 엣지를 가지며 시간에 따라 변하는 추천 데이터에 적용하는 것이 매우 어렵습니다.

해당 논문에서는 높은 scailability를 가지고 있는 random walk기반 GCN 모델을 제안하였습니다.

PinSage를 요약하자면 다음과 같습니다.

Scailability

  • On-the-fly convolution (Transductive vs. Inductive)
    기존 GCN은 full-graph에서 연산을 진행한 반면, PinSage는 target node를 선정한 뒤 이웃을 sampling하는 방식(computation graph를 생성)으로 진행합니다. 따라서 전체 그래프에 해당하는 연산을 필요로 하는 GCN의 단점을 완화시켰습니다.

  • Producer-consumer minibatch construction
    Producer와 consumer의 역할을 CPU와 GPU로 나누어 진행하였습니다. CPU를 computation graph 생성을 위한 sampling을 진행하고, GPU는 생성된 computation graph로 모델 학습을 진행합니다.

  • Efficient MapReduce inference
    MapReduce와 같은 파이프라인을 설계하여 반복적인 연산을 최소화하면서 빠르게 임베딩 벡터를 생성할 수 있습니다.

New techniques

  • Constructing convolutions via random walks
    효율적인 연산을 위해 computation graph를 미리 생성한다고 하였습니다. 이때, 무작위하기 이웃을 생성하는 것은 비효율적이기 때문에, short random walk를 사용합니다.

  • Importance pooling
    Random walk를 활용해 노드들끼리 유사성(similarity)을 구할 수 있습니다. 해당 논문에서는 이 유사성을 importance score로 정의하였으며, 이를 aggretation과 pooling 단계에 사용하여 가중(weighted)연산을 하였고, 46% 성능 증가를 가져왔습니다.

Figure 1: Overview of our model architecture using depth-2 convolutions

  • Curriculum training
    학습을 진행할 때마다 좀 더 어려운 예시를 모델에 보여줌(curriculum traning)으로써, 12%의 성능 증가를 가져왔습니다.

Method

PinSage의 구조, 학습 방식, MapRudece pipleline에 대해 살펴보겠습니다.

  • Node: item (pin and board)
  • Feature: visual, textual feature

Problem setup

Pinterest의 contents인 pin은 유저의 주 관심사이며, board는 pin의 collections입니다. 해당 추천시스템은 이러한 pins를 잘 임베딩하고자 하는 것입니다. 임베딩을 위해 그래프를 정의해야 하는데, 여기서는 pin의 집합 II 와 board의 집합 CC을 이분 그래프(bipartite graph)로 생성하였습니다.

Bipartite graph, Chapter 19, CS224W

Notations
II: set of items
CC: user-defined contexts
uIu \in I: pin/item
xuRdx_u \in \mathbb{R}^d: real-valued attributes (content information, i.e., text and image feature)

Goal
bipartite graph와 node feature xux_u를 활용하여 node embedding을 수행함.

Model Architecture

Localized convolution

Step 1: zv,vN(u)z_v, \forall v \in \mathcal{N}(u)를 linear layer로 변형함.
Step 2: aggregation/pooling γ\gamma 적용하여 nun_u 벡터 생성함.
Step 3: 노드의 벡터 zuz_u와 aggregation된 이웃 벡터 nun_u를 concatenate, linear layer로 변형함.
Step 4: nomalization

Inportance-based neighborhoods(Importance pooling)
PinSage에서 핵심인 inportance score에 대해 살펴봅시다. 기존의 GCN과 다르게, PinSage는 타겟 노드에게 상대적으로 많은 영향을 주는 노드들을 선별하여 aggregate/pooling을 진행하였습니다.

Step 1: 타겟 노드 uu에서 random walk를 시작함.
Step 2: random walk로 방문한 노드들의 방문 횟수를 계산함.
Step 3: 타겟 노드 uu의 이웃들 중에서 이전 스텝에서 계산한 값 상위 T개를 선출함.

해당 밥법은 두 가지 관점에서 이점을 가져옵니다.

  • 메모리를 줄일 수 있다.
  • 중요한 이웃들만 고려하여 노드를 업데이트 시킬 수 있다.

또한 Step 2에서 계산한 값을 L1L_1 normarlization을 하여 aggregate/pooling의 weight으로 사용하였습니다.

Stacking convolutions

하나의 Convolution layer 파라미터는 Q,q,W,wQ, q, W, w가 있으며, node들끼리 공유하게 됩니다. Algorithm2는 minibatch에 어떻게 convolution layers를 적용하는 지 보여줍니다.

Convolution이 끝난 후 생성된 target node의 representation은 linear layers를 한 번 더 거치게 되고, 최종 output embedding이 만들어지게 됩니다.

모델 파라미터 정리:
각 convolution layer의 weight과 bias: Q,q,W,wQ, q, W, w
마지막 linear layer: G1,G2,gG_1,G_2, g

Model Training

PinSage는 max-margin ranking loss를 학습에 사용하며, item pair인 (q,i)L(q,i)\in \mathcal{L}을 가깝도록 임베딩하게 됩니다.

수십억 개의 embedding을 학습하기 위해 어떻게 효율적으로 연산을 했는지 살펴보도록 하겠습니다.

Loss function
Basic idea: postive pair의 내적을 최대로 만들고, negative pair의 내적값을 미리 정의한 margin Δ\Delta만큼 거리를 유지하게 만들자.

, where Pn(q)P_n(q)은 negative sample의 분포입니다.

Multi-GPU training with large minibatches
Producer-consumer minibatch constructions

Sampling negative items
PinSage는 학습의 효율을 개선하기 위해 500개의 negative sample을 minibatch마다 공유할 수 있도록 하였습니다.
해당 논문에서는 두 가지의 sampling 방법을 제안하였습니다.

  • 무작위 샘플링 (unifonly sample)
    전체 아이템세트에서 무작위로 negative item을 뽑는 것으로, postive와 negative를 구분하기 매우 쉽다.
  • Hard negative sampling
    "hard" negative item을 negative sample로 정하여 학습시키 방법으로, positive sample은 아니지만, 상대적으로 가까운 negative sample을 뽑는 방법이다. Personalized PageRank score(C. Eksombatchai, et al.(2018))를 활용하여 item의 score를 결정하게 되고, 2000-5000위 사이의 ranked item을 뽑게 된다.

논문에서는 hard negative sample을 학습에 사용하면, 수렴을 위해 2배의 epoch이 요구된다고 하였습니다. 이를 해결하기 위해, 처음부터 har sample을 사용하는 것이 아닌, 학습을 진행할수록 hard negative sample을 하나씩 추가하는 curriculum training을 적용하였습니다.

Figure 2: Random negative examples and hard negative examples

Node Embeddings vis MapReduce

모델 학습이 끝난 후에, 학습 데이터의 모든 아이템과 그 외의 아이템을 임베딩하는 것은 계산적으로 매우 어려운 일입니다. 따라서 해당 논문에서는 MapReduce approach를 개발하였으며, 반복적인 계산을 줄여 효율적인 연산이 가능하도록 하였습니다.

Figure 3: Node embedding data flow to compute the first layer representation using MapReduce

Experiments

평가를 위해 두 가지 태스크를 진행하였습니다.

  • Recommending related pins
    Related pin을 추천하기 위해 임베딩 공간에서 k nearest neighbor를 선택합니다.

  • Recommending pins in a user's home/news feed
    Pin을 추천하기 위해, 유저가 가장 최근에 추가한 아이템과 임베딩 공간에서 가장 가까운 아이템을 추천합니다.

Chapter 19, CS224W

Feature used for learning
각각의 pin은 text(title)과 image 데이터와 관련되어 있습니다. 따라서 visual embedding(VGG-16, d=4096d=4096), textual embedding (Word2Vec, d=256d=256)를 concatenate하여 node feature를 생성합니다.

Baselines for comparison

  • Visual embedding: 이미지 임베딩 공간에서 nearest neighbor 사용
  • Annotation embedding: annotation 임베딩 공간에서 nearest neighbor 사용
  • Combined embedding: visual + annotation 벡터에 2-layer multi-layer 모델을 사용
  • Graph-based method: random-walk-based 방법을 사용하여 타겟 pin의 top K 이웃을 추천

Table 1: Hit-rate and MRR for PinSage and content-based deep learning baselines

Conclusion

  • 해당 논문은 random-walk graph convolutional network를 활용한 PinSage라는 모델을 제안하였습니다.
  • PinSage는 기존의 GCN 모델이 가지고 있던 scailability의 한계를 극복하기 위해 inductive setting과 MapReduce와 같은 알고리즘을 활용하였습니다.
  • 실제 성능과 효율성을 측정하기 위해 A/B test를 진행하였고, 좋은 결과를 보여주었습니다.
profile
2021 투빅스 추천시스템 세미나입니다.

4개의 댓글

comment-user-thumbnail
2021년 5월 30일

[15기 이성범]
본 논문은 Pinterest에서 사용되는 추천 알고리즘인 PinSage에 대하여 소개된 논문이다. PinSage는 Pinterest와 GraphSage가 합쳐진 이름이다. GraphSage는 Graph Convolutional Network의 발전된 형태로 서로 연결된 노드, 혹은 정점들은 비슷한 정보를 가질 것이라는 가정하에 어떤 정점의 feature를 만들기 위해서 주변의 정보를 활용하는 형태의 알고리즘이다. 즉, 적절한 수의 주변의 노드를 샘플링하여 학습시킴으로써 GCN의 연산 속도를 개선한 알고리즘이라고 할 수 있다.

PinSage모델은 기존의 GCN의 연산 속도를 개선시키기 위해서 tager Node를 선정 한 후 이웃을 샘플링하는 방식으로 학습이 진행되고, 그래프 데이터 생성 및 샘플링에는 CPU를 활용하고 모델 학습에는 GPU가 활용된다. 또한 MapReduce와 같은 파이프라인을 설계하여 반복적인 연산을 최소화하여 빠르게 임베딩 벡터를 생성한다. 그리고 효율적인 연산을 위해서 그래프 데이터를 미리 생성하며 이웃 생성시에는 Short Random Walk 방식을 활용한다. Random Walk를 통해서 노드들의 유사성도 capture할 수 있다. 또 학습 진행될 때 마다 조금 더 어려운 예시를 보여줌으로써 모델의 성능을 향상시켰다.

PinSage는 유저의 주 관심사인 pin과 pin의 collection인 board를 이분그래프 형식으로 설정해 데이터를 구성한다. 모델의 목적은 pin을 잘 임베딩 하는 것이다. 학습 시에 타겟 노드에게 상대적으로 많은 영향을 주는 노드들을 선별하여 aggregate/pooling을 진행한다. 이러한 방식으로 학습이 진행되면 중요한 이웃들만 고려하여 노드를 업데이트 시킬 수 있으며, 메모리를 줄일 수 있다는 장점을 가진다. Convolution이 종료된 후 생성된 target 노드의 Representation을 선형 레이어를 한번 더 거쳐서 최종 Embedding을 만든다. 만들어진 Embedding은 k-NN 알고리즘을 활용하여 가장 유사한 pin을 추천해주는 식으로 활용된다. 결론적으로 본 논문에서 제시된 알고리즘은 A/B Test 결과 좋은 성능을 보여줬고 유사한 pin을 추천해준다고 한다.

답글 달기
comment-user-thumbnail
2021년 6월 1일

[15기 장아연]

PinSage는 핀터레스트(Pinterest)에 적용된 추천알고리즘임. GCN 모델로, 그래프 데이터에 랜덤 워크(randowm walks)와 graph convolution을 적용함.

기존의 Graph Convolutional Network는 이웃으로부터 특정 정보를 반복적으로 aggregate하는 것을 학습하는 것으로 convolution 연산을 사용해 one-hop 이웃들의 정보를 transform하고 aggregate하여 이 layer를 여러개 쌓아 정보를 계속해서 변형하고 모아 멀리 있는 곳까지 닿음. 그러나 이러한 방식에는 scailability가 떨어져 추천 시스템에 적용하기 어려움.

그리하여 높은 scailability를 가지고 있는 random walk기반 GCN 모델을 제안함. Scailability는 On-the-fly convolution, Producer-consumer minibatch construction, Efficient MapReduce inference를 통해 구현함. Constructing convolutions via random walks, Importance pooling, Curriculum training를 새롭게 적용하여 성능을 높임.

Pinsage는 board를 이분그래프로 설정해 데이터를 구성하고 영향력이 강한 node에 대해서는 aggregation과 pooling을 하고 update하는 convolution을 거치고 linear layer를 거쳐 board를 구성하는 pin에 대한 표현력이 높은 Embedding을 구현함. 그리고 KNN을 이용해 유사한 것을 추천함.

답글 달기

[15기 김현지]
PinSage는 실제 서비스 되고 있는 핀터레스트에 적용된 추천알고리즘이다. 이는 GCN모델로, 그래프 데이터에 랜덤 워크와 graph convolution을 적용하였다.
GCN-based 모델은 scailability가 떨어지기 때문에 시간에 따라 변하는 추천 데이터에 적용하는 것이 매우 어려운데, 해당 논문에서는 높은 scailability를 가지고 있는 random walk 기반의 GCN모델을 제안하였다.
PinSage는 one-the-fly convolution과 producer-consumer minibatch construction, Efficient MapReduce inference로 Scailability를 확보하였고, Constructing convolutions via random walks와 importance pooling이라는 새로운 기법을 도입하여 성능을 향상시켰다.

Method
해당 추천시스템은 핀터레스트의 컨텐츠인 pins을 잘 임베딩하고자 하며, 임베딩을 위해 pin의 집합 I와 pin의 collections인 board의 집합 C를 이분그래프로 생성하였다. 이러한 이분 그래프와 노드 피쳐를 활용하여 노드 임베딩을 수행한다.

Importance pooling
기존 GCN과 다르게, 타겟 노드에게 상대적으로 영향을 많이 주는 노드들을 선별하여 aggregate/pooling을 진행하였다. 이 방법은 메모리를 줄임과 동시에 중요한 이웃들만 고려해 노드들을 업데이트 시킨다는 이점이 있다.

Model Training
max-margin ranking loss를 학습에 사용하며, item pair인 (q,i)∈L을 가깝도록 임베딩하게 된다. negative sample을 minibatch마다 공유할 수 있도록하여 학습의 효율을 개선하였다.

Node Embedding vis MapReduce
모델 학습이 끝난 후에는 논문의 저자들이 개발한 MapReduce approch로 학습 데이터의 아이템을 임베딩을 구현하였다.

Experiments
평가를 위해서는 임베딩 공간에서 knn을 선택하여 추천하는 것과 유저가 가장 최근에 추가한 아이템과 임베딩 공간에서 가장 가까운 아이템을 추천하는 테스크를 진행하였으며 좋은 결과를 보여주었다.

답글 달기
comment-user-thumbnail
2021년 6월 1일

[Paper Review] (2018, KDD) Graph Convolutional Neural Networks for Web-Scale Recommender System
15기 류채은

PinSage:

  • 실제 서비스 되고 있는 핀터레스트(Pinterest)에 적용된 추천 알고리즘
  • GCN 모델로, 그래프 데이터에 랜덤 워크(randowm walks)와 graph convolution을 적용한 방법론 (GCN의 핵심은 이웃들(neighbohoods)로부터 특징 정보를 반복적으로 모으는(aggregate) 방법을 학습하는 것)

[Scailability]

  • On-the-fly convolution (Transductive vs. Inductive)
  • Producer-consumer minibatch construction
  • Efficient MapReduce inference

[Pinsage 모델 구조]

  • Inportance-based neighborhoods(Importance pooling(타겟 노드에게 상대적으로 많은 영향을 주는 노드들 선별 -> aggregate/pooling을 진행)
  • Stacking convolutions
  • Convolution이 끝난 후 생성된 target node의 representation은 linear layers를 한 번 더 거치게 되고, 최종 output embedding이 만들어지게 됨

[Sampling negative items]

  • Sampling negative items
  • Hard negative sampling
답글 달기